Pourquoi le tri par sélection est-il plus rapide que le tri par bulles?

28

Il est écrit sur Wikipedia que "... le tri par sélection surpasse presque toujours le tri par bulles et le tri par gnomes." Quelqu'un peut-il m'expliquer pourquoi le tri par sélection est considéré plus rapide que le tri par bulles, même si les deux ont:

  1. Pire complexité du temps : O(n2)

  2. Nombre de comparaisons : O(n2)

  3. Meilleur temps de complexité :

    • Tri des bulles: O(n)
    • Tri de sélection: O(n2)
  4. Complexité moyenne en temps de cas :

    • Tri des bulles: O(n2)
    • Tri de sélection: O(n2)
RYO
la source

Réponses:

32

Toutes les complexités que vous avez fournies sont vraies, mais elles sont notation Big O , donc toutes les valeurs et constantes additives sont omises.

Pour répondre à votre question, nous devons nous concentrer sur une analyse détaillée de ces deux algorithmes. Cette analyse peut être effectuée à la main ou trouvée dans de nombreux livres. J'utiliserai les résultats de Knuth's Art of Computer Programming .

Nombre moyen de comparaisons:

  • Tri des bulles : 12(N2NlnN(γ+ln21)N)+O(N)
  • Tri par insertion : 14(N2N)+NHN
  • Tri de sélection : (N+1)HN2N

Maintenant, si vous tracez ces fonctions, vous obtenez quelque chose comme ceci: terrain plot2

Comme vous pouvez le voir, le tri à bulles est bien pire à mesure que le nombre d'éléments augmente, même si les deux méthodes de tri ont la même complexité asymptotique.

Cette analyse est basée sur l'hypothèse que l'entrée est aléatoire - ce qui pourrait ne pas être vrai tout le temps. Cependant, avant de commencer le tri, nous pouvons permuter aléatoirement la séquence d'entrée (en utilisant n'importe quelle méthode) pour obtenir le cas moyen.

J'ai omis l'analyse de la complexité temporelle car cela dépend de la mise en œuvre, mais des méthodes similaires peuvent être utilisées.

Bartosz Przybylski
la source
J'ai un problème avec "nous pouvons permuter aléatoirement la séquence d'entrée pour obtenir un cas moyen". Pourquoi cela peut-il être fait plus rapidement que le temps nécessaire pour trier?
Sasho Nikolov
1
NNO(NlogN)N
Je suppose que j'avais sommeil, vous avez raison, la séquence peut être permutée en temps linéaire.
Sasho Nikolov
HN=Θ(logN)
Gamma = 0,577216 est la constante d'Euler-Mascheroni. Le chapitre correspondant est "L'art de la programmation" vol 3 section 5.2.2 p. 109 et 129. Comment avez-vous tracé le cas de tri des bulles exactement en particulier le terme O (sqrt (N))? Vous venez de le négliger?
mxmlnkn
11

O -notation, décrit le comportement limitant d'une fonction car son argument tend vers l'infini, c'est-à-dire son taux de croissance.

La fonction elle-même, par exemple le nombre de comparaisons et / ou de swaps, peut être différente pour deux algorithmes avec le même coût asymptotique, à condition qu'ils croissent avec le même taux.

n/41 (une fois le minimum / maximum a été trouvé, il est échangé une fois à la fin du tableau).

k×nkn/2(n1)×(n2)/2 comparaisons .

En résumé, la limite asymptotique vous donne une bonne idée de la façon dont les coûts d'un algorithme augmentent par rapport à la taille d'entrée, mais ne dit rien sur les performances relatives des différents algorithmes dans le même ensemble.

Pedro
la source
1
c'est même une très bonne réponse
Grijesh Chauhan
quel livre préférez-vous?
Grijesh Chauhan
@GrijeshChauhan: Les livres sont une question de goût, alors prenez toute recommandation avec un grain de sel. Personnellement, j'aime "Introduction to Algorithms" de Cormen, Leiserson et Rivest, qui donne un bon aperçu sur un certain nombre de sujets, et la série "The Art of Computer Programming" de Knuth si vous avez besoin de plus / tous les détails sur un sujet spécifique. Vous voudrez peut-être vérifier si la question des livres a déjà été posée ici, ou poster cette question si ce n'est pas le cas.
Pedro
Pour moi, le troisième paragraphe de votre réponse est la vraie réponse. Pas les graphiques pour les grandes entrées, donnés dans d'autres réponses.
suréchange
3

Le tri à bulles utilise plus de temps d'échange, tandis que le tri par sélection évite cela.

Lors de l'utilisation de la sélection, le tri permute nau maximum les heures. mais lorsque vous utilisez le tri à bulles, il échange presque n*(n-1). Et évidemment, le temps de lecture est inférieur au temps d'écriture, même en mémoire. Le temps de comparaison et les autres temps de fonctionnement peuvent être ignorés. Les temps d'échange sont donc le goulot d'étranglement critique du problème.

simonmysun
la source
Je pense que l'autre réponse de Bartek est plus raisonnable mais je ne peux pas voter ou commenter ... BTW Je pense toujours que le temps d'écriture affecte plus et j'espère qu'il pourra prendre cela en considération s'il le voit et qu'il est d'accord.
simonmysun
Vous ne pouvez pas simplement ignorer le nombre de comparaisons, car il existe des cas d'utilisation où le temps passé à comparer deux éléments peut dépasser de loin le temps passé à échanger deux éléments. Considérez une liste chaînée de chaînes extrêmement longues (disons 100 000 caractères chacune). La lecture de chaque chaîne prendrait beaucoup plus de temps que la réaffectation du pointeur.
Irvin Lim
@IrvinLim Je pense que vous avez peut-être raison, mais je devrai peut-être voir les données statistiques avant de changer d'avis.
simonmysun