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

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

Pour répondre à votre question, nous avons besoin d se concentrer sur une analyse détaillée de ces deux algorithmes. Cette analyse peut être faite à la main ou trouvée dans de nombreux livres. Jutiliserai les résultats de Knuth « s Art of Computer Programming .

Nombre moyen de comparaisons:

• Tri par bulles : $ \ frac {1} {2} (N ^ 2-N \ ln N – (\ gamma + \ ln2 -1) N) + \ mathcal O (\ sqrt N) $
• Tri par insertion : $ \ frac {1} {4} (N ^ 2-N) + N – H_N $
• Tri par sélection : $ (N + 1) H_N – 2N $

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

Comme vous pouvez le voir, le tri par 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 asymptotique complexité.

Cette analyse est basée sur lhypothèse que lentrée est aléatoire – ce qui peut ne pas être vrai tout le temps. Cependant, avant de commencer le tri, nous pouvons permuter aléatoirement la séquence dentrée (en utilisant nimporte quelle méthode) pour obtenir le cas moyen.

Jai omis lanalyse de complexité temporelle car elle dépend de limplémentation, mais des méthodes similaires peuvent être utilisées.

Commentaires

• Jai un problème avec  » nous pouvons permuter aléatoirement la séquence dentrée pour obtenir la casse moyenne « . Pourquoi cela peut-il être fait plus rapidement que le temps requis pour trier?
• Vous pouvez permuter nimporte quelle séquence de nombres, cela prendra $ N $ temps où $ N $ est la longueur de la séquence. Il est ‘ évident que tout algorithme de tri basé sur la comparaison doit avoir au moins $ \ mathcal O (N \ log N) $ complexité donc même si vous y ajoutez $ N $ ‘ la complexité de ‘ na pas été tellement modifiée. Quoi quil en soit, nous parlons de comparaison et non de temps, la complexité du temps dépend de la mise en œuvre et de la machine en cours dexécution, comme je lai mentionné dans la réponse.
• Je suppose que javais sommeil, vous avez raison, la séquence peut être permutée en temps linéaire .
• Puisque $ H_N = \ Theta (log N) $, votre borne de comparaison est-elle correcte pour le tri par sélection? Il semble que vous ‘ impliquer quil effectue des comparaisons O (n log n) en moyenne.
• Gamma = 0,577216 est Euler-Mascheroni . Le chapitre pertinent est  » Lart de la programmation  » vol 3 section 5.2.2 pg. 109 et 129. Comment avez-vous tracé exactement le cas du tri à bulles, en particulier le terme O (sqrt (N))? Lavez-vous simplement négligé?

Le coût asymptotique, ou $ \ mathcal O $ -notation, décrit le comportement limitant dune fonction lorsque son argument tend vers linfini, cest-à-dire son taux de croissance.

La fonction elle-même, par exemple le nombre de comparaisons et / ou de swaps, peut être différent pour deux algorithmes ayant le même coût asymptotique, à condition quils croissent au même rythme.

Plus précisément, le tri à bulles nécessite en moyenne n / 4 $ $ swaps par entrée (chaque entrée est déplacée élément par élément de sa position initiale à sa position finale, et chaque swap implique deux entrées), tandis que le tri par sélection ne nécessite que 1 $ $ (une fois que le minimum / maximum a été trouvé, il est échangé une fois à la fin du tableau).

En termes de nombre de comparaisons, le tri à bulles nécessite $ k \ fois n $ comparaisons, où $ k $ est la distance maximale entre la position initiale dune entrée et sa position finale, qui est généralement plus grande que $ n / 2 $ pour les valeurs initiales uniformément distribuées. Le tri par sélection, cependant, nécessite toujours des comparaisons $ (n-1) \ times (n-2) / 2 $.

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

Commentaires

• cest même une très bonne réponse
• quel livre préférez-vous?
• @GrijeshChauhan: Les livres sont une question de goût, alors prenez toute recommandation avec un grain de sel. Jaime personnellement Cormen, Leiserson et Rivest ‘ s  » Introduction aux algorithmes « , qui donne un bon aperçu sur un certain nombre de sujets, et Knuth ‘ s  » Lart de la programmation informatique  » série 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 publier cette question si elle n’a pas ‘ t.
• Pour moi, troisième paragraphe de votre réponse est la vraie réponse. Pas les graphiques pour les grandes entrées, donnés dans une autre réponse.

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

Lors de lutilisation de la sélection de tri, il échange n fois au maximum. mais lors de lutilisation du 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 de permutation sont donc le goulot détranglement critique du problème.

Commentaires

• Je pense que lautre réponse de Bartek est plus raisonnable mais je peux ‘ voter ou commenter … BTW Je pense toujours que le temps décriture affecte plus et jespère quil pourra prendre cela en considération sil le voit et laccepte.
• Vous ne pouvez pas simplement ignorer le nombre de comparaisons, car il y a des cas dutilisation où le temps dépensé pour comparer deux éléments peut largement dépasser 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.
• @IrvinLim Je pense que vous avez peut-être raison, mais je devrai peut-être voir les données statistiques avant de changer davis.