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

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 : $\mathcal O(n^2)$

2. Nombre de comparaisons : $\mathcal O(n^2)$

3. Meilleur temps de complexité :

   • Tri des bulles: $\mathcal O(n)$
   • Tri de sélection: $\mathcal O(n^2)$

4. Complexité moyenne en temps de cas :

   • Tri des bulles: $\mathcal O(n^2)$
   • Tri de sélection: $\mathcal O(n^2)$

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 : $\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 de 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 à 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.

$\mathcal 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/4$$1$ (une fois le minimum / maximum a été trouvé, il est échangé une fois à la fin du tableau).

$k\times n$$k$$n/2$$(n-1)\times(n-2)/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.

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.