Devinez par manque de contexte - vous posez des questions sur un tri en mémoire sans obligation de répandre les résultats intermédiaires sur le disque?
Jonathan Leffler
1
Selon ces animations, le tri par insertion fonctionne mieux sur les données principalement triées.
dopple
Réponses:
259
Basé sur la méthode hautement scientifique de regarder des gifs animés, je dirais que les types d'insertion et de bulles sont de bons candidats.
Le tri à bulles est terrible. C'est toujours O (n ^ 2). Supprimez au moins cela de votre réponse pour qu'elle soit juste s'il vous plaît.
jjnguy
79
jjnguy, c'est tout simplement faux. Je pense que vous devez reprendre votre classe d'algorithmes. Sur des données presque triées (c'est le cas adaptatif), c'est O (N). Cependant, il faut 2 passages à travers les données et l'insertion n'en prend que 1 pour les données presque triées, ce qui fait de l'insertion le gagnant. La bulle est toujours bonne
mmcdole
3
Les performances se dégradent très gravement si vos données ne sont jamais presque triées. Je ne l'utiliserais toujours pas, personnellement.
C'est exactement le genre de réponse que je cherchais, j'ai lu des livres mais je ne semble pas trouver d'explication claire pour la sélection d'alogorithmes dans des cas particuliers, pourriez-vous s'il vous plaît préciser ceci ou passer un lien afin que je puisse un peu plus? Merci
Simran kaur
9
Vous devez ajouter "Les données sont déjà triées selon un autre critère => FUSIONNER LE TRI"
Jim Hunziker
30
Timsort
Timsort est "une fusion adaptative, stable et naturelle" avec "des performances surnaturelles sur de nombreux types de tableaux partiellement ordonnés (moins de comparaisons lg (N!) Nécessaires, et aussi peu que N-1)". Intégré à Pythonsort()utilise cet algorithme depuis un certain temps, apparemment avec de bons résultats. Il est spécialement conçu pour détecter et tirer parti des sous-séquences partiellement triées dans l'entrée, qui se produisent souvent dans des ensembles de données réels. Il arrive souvent dans le monde réel que les comparaisons coûtent beaucoup plus cher que d'échanger des éléments dans une liste, car on n'échange généralement que des pointeurs, ce qui fait très souvent de timsort un excellent choix. Cependant, si vous savez que vos comparaisons sont toujours très bon marché (écrire un programme jouet pour trier des entiers 32 bits, par exemple), il existe d'autres algorithmes qui sont susceptibles de mieux fonctionner. Le moyen le plus simple de tirer parti du tri temporel est bien sûr d'utiliser Python, mais comme Python est open source, vous pourrez peut-être également emprunter le code. Sinon, la description ci-dessus contient plus que suffisamment de détails pour écrire votre propre implémentation.
@JF Sebastian: timsort est beaucoup plus rapide que les lg(n!)comparaisons sur un tableau presque trié, jusqu'à O(n)! | @behrooz: Aucun tri de comparaison ne peut avoir un cas moyen supérieur à O(n log n)et lg(n!)est O(n log n). Le pire des cas de Timsort n'est donc asymptotiquement pas pire que celui de tout autre type de comparaison. De plus, son meilleur cas est meilleur ou égal à tout autre type de comparaison.
Artelius
3
Timsort est toujours O (nlogn) dans le pire des cas, mais ses bons-cas sont assez agréables. Voici une comparaison, avec quelques graphiques: stromberg.dnsalias.org/~strombrg/sort-comparison Notez que timsort en Cython n'était pas aussi rapide que timsort intégré à Python en C.
user1277476
19
Tri par insertion avec le comportement suivant:
Pour chaque élément kdans les emplacements 1..n, vérifiez d'abord si el[k] >= el[k-1]. Si tel est le cas, passez à l'élément suivant. (Évidemment, sautez le premier élément.)
Sinon, utilisez la recherche binaire dans les éléments 1..k-1pour déterminer l'emplacement d'insertion, puis parcourez les éléments. (Vous ne pouvez le faire que si k>Toù Test une valeur de seuil; avec un petit, kc'est exagéré.)
Je pense que le tri à bulles pourrait battre cela si le nombre d'éléments non triés est très petit (comme un ou deux), mais en général, cela me semble probablement la meilleure solution.
Sol
En raison de l'étape 1, pour tous les éléments déjà triés, il y a exactement une comparaison et zéro déplacement de données, ce qui est évidemment le mieux que vous puissiez faire. L'étape 2 est celle que vous pourriez améliorer, mais la bulle déplacera le même nombre d'éléments et pourrait avoir plus de comparaisons, en fonction de votre impl.
Jason Cohen
En fait, après réflexion, je pense que le tri des bulles est plus fort que je ne le pensais. C'est en fait une question assez délicate. Par exemple, si vous prenez le cas où la liste est entièrement triée sauf que l'élément qui devrait être le dernier est le premier, le tri à bulles surpassera largement ce que vous décrivez.
Sol
J'ai essayé de l'implémenter mais la recherche binaire n'est pas une grande amélioration car vous devez toujours déplacer le bloc entier pour insérer l'élément. Donc, au lieu de 2xrange, vous obtenez range + logb (range).
Il est basé sur le tri rapide, mais il évite le pire des cas de comportement du tri rapide pour les listes presque triées.
L'astuce est que cet algorithme de tri détecte les cas où le tri rapide passe dans le mode le plus défavorable et passe au tri par tas ou par fusion. Les partitions presque triées sont détectées par une méthode de partition non naiive et les petites partitions sont gérées à l'aide du tri par insertion.
Vous obtenez le meilleur de tous les principaux algorithmes de tri pour le coût d'un code et d'une complexité accrus. Et vous pouvez être sûr que vous ne rencontrerez jamais le pire des cas, quelle que soit l'apparence de vos données.
Si vous êtes un programmeur C ++, vérifiez votre algorithme std :: sort. Il peut déjà utiliser un tri introspectif en interne.
Splaysort est une méthode de tri obscure basée sur des arbres splay , un type d'arbre binaire adaptatif. Splaysort est bon non seulement pour les données partiellement triées, mais aussi pour les données partiellement triées inversement, ou en fait pour toutes les données qui ont un ordre préexistant. C'est O (nlogn) dans le cas général, et O (n) dans le cas où les données sont triées d'une manière ou d'une autre (avant, arrière, orgue, etc.).
Son grand avantage par rapport au tri par insertion est qu'il ne revient pas au comportement O (n ^ 2) lorsque les données ne sont pas du tout triées, vous n'avez donc pas besoin d'être absolument sûr que les données sont partiellement triées avant de les utiliser .
Son inconvénient est la surcharge d'espace supplémentaire de la structure d'arbre splay dont elle a besoin, ainsi que le temps nécessaire pour construire et détruire l'arbre splay. Mais en fonction de la taille des données et de la quantité de pré-tri que vous attendez, la surcharge peut en valoir la peine pour l'augmentation de la vitesse.
Le tri en douceur de Dijkstra est un excellent tri sur les données déjà triées. C'est une variante heapsort qui s'exécute dans le pire des cas O (n lg n) et dans le meilleur des cas O (n). J'ai écrit une analyse de l'algorithme, au cas où vous seriez curieux de savoir comment cela fonctionne.
Le tri de fusion naturel est un autre très bon pour cela - c'est une variante de tri de fusion ascendante qui fonctionne en traitant l'entrée comme la concaténation de plusieurs plages triées différentes, puis en utilisant l'algorithme de fusion pour les joindre. Vous répétez ce processus jusqu'à ce que toute la plage d'entrée soit triée. Cela s'exécute dans le temps O (n) si les données sont déjà triées et dans le pire des cas O (n lg n). C'est très élégant, bien qu'en pratique ce ne soit pas aussi bon que d'autres types adaptatifs comme Timsort ou smoothsort.
quelles sont les constantes d'exécution de smoothsort par rapport aux autres algorithmes de tri? (ie runtime (smoothsort) / runtime (insertionsort) pour les mêmes données)
Arne Babenhauserheide
4
Si les éléments sont déjà triés ou s'il n'y a que peu d'éléments, ce serait un cas d'utilisation parfait pour le tri par insertion!
Le tri par insertion prend du temps O (n + le nombre d'inversions).
Une inversion est une paire (i, j)telle que i < j && a[i] > a[j]. Autrement dit, une paire dans le désordre.
Une mesure de «presque triés» est le nombre d'inversions - on pourrait prendre «des données presque triées» pour signifier des données avec peu d'inversions. Si l'on sait que le nombre d'inversions est linéaire (par exemple, vous venez d'ajouter des éléments O (1) à une liste triée), le tri par insertion prend O (n) temps.
Comme tout le monde l'a dit, faites attention au tri rapide naïf - qui peut avoir des performances O (N ^ 2) sur des données triées ou presque triées. Néanmoins, avec un algorithme approprié pour le choix du pivot (aléatoire ou médian sur trois - voir Choisir un pivot pour Quicksort ), Quicksort fonctionnera toujours correctement.
En général, la difficulté de choisir des algorithmes tels que le tri par insertion est de décider quand les données sont suffisamment désordonnées pour que Quicksort soit vraiment plus rapide.
Je ne vais pas prétendre avoir toutes les réponses ici, car je pense que pour obtenir les réponses réelles, il faudra peut-être coder les algorithmes et les profiler par rapport à des échantillons de données représentatifs. Mais j'ai réfléchi à cette question toute la soirée, et voici ce qui m'est arrivé jusqu'à présent, et quelques suppositions sur ce qui fonctionne le mieux où.
Soit N le nombre total d'articles, M le nombre en désordre.
Le tri à bulles devra faire quelque chose comme 2 * M + 1 passes à travers tous les N éléments. Si M est très petit (0, 1, 2?), Je pense que ce sera très difficile à battre.
Si M est petit (disons moins que log N), le tri par insertion aura de bonnes performances moyennes. Cependant, à moins qu'il n'y ait un truc que je ne vois pas, il aura de très mauvaises performances dans le pire des cas. (Non? Si le dernier élément de la commande vient en premier, vous devez insérer chaque élément, pour autant que je puisse voir, ce qui va tuer les performances.) Je suppose qu'il existe un algorithme de tri plus fiable pour cela cas, mais je ne sais pas ce que c'est.
Si M est plus grand (disons égal ou grand que log N), le tri introspectif est presque certainement le meilleur.
Exception à tout cela: si vous savez réellement à l'avance quels éléments ne sont pas triés, alors votre meilleur pari sera de retirer ces éléments, de les trier en utilisant un tri introspectif et de fusionner les deux listes triées en une seule liste triée. Si vous pouviez rapidement déterminer quels articles sont en panne, ce serait également une bonne solution générale - mais je n'ai pas été en mesure de trouver un moyen simple de le faire.
Réflexions supplémentaires (pendant la nuit): Si M + 1 <N / M, vous pouvez parcourir la liste à la recherche d'une série de N / M dans une ligne qui est triée, puis étendre cette course dans les deux sens pour trouver le hors de -Items commandés. Cela prendra au plus 2N comparaisons. Vous pouvez ensuite trier les éléments non triés et effectuer une fusion triée sur les deux listes. Les comparaisons totales devraient être inférieures à quelque chose comme 4N + M log2 (M), ce qui va battre toute routine de tri non spécialisée, je pense. (Encore plus de réflexion: c'est plus délicat que je ne le pensais, mais je pense toujours que c'est raisonnablement possible.)
Une autre interprétation de la question est qu'il peut y avoir de nombreux articles dans le désordre, mais ils sont très proches de l'endroit où ils devraient être dans la liste. (Imaginez commencer par une liste triée et échanger tous les autres éléments avec celui qui suit.) Dans ce cas, je pense que le tri à bulles fonctionne très bien - je pense que le nombre de passes sera proportionnel au plus éloigné d'un élément est. Le tri par insertion fonctionnera mal, car chaque élément hors service déclenchera une insertion. Je soupçonne que le tri introspectif ou quelque chose comme ça fonctionnera bien aussi.
Si vous avez besoin d'une implémentation spécifique pour les algorithmes de tri, les structures de données ou tout ce qui a un lien avec ce qui précède, puis-je vous recommander l'excellent projet "Structures de données et algorithmes" sur CodePlex?
Il aura tout ce dont vous avez besoin sans réinventer la roue.
Cette belle collection d'algorithmes de tri à cet effet dans les réponses, semble manquer de Gnome Sort , qui conviendrait également, et nécessite probablement le moins d'effort de mise en œuvre.
Le tri par insertion est le meilleur des cas O (n) sur une entrée triée. Et c'est très proche sur les entrées principalement triées (mieux que le tri rapide).
La cohérence n'est pas préoccupante ici. Heapsort donnera O (n lg n) même sur des données triées, et n'est pas vraiment adaptatif. Les options viables peuvent être: le tri par insertion, Timsort et Bubblesort.
Max
0
Le tri à bulles (ou, plus sûr encore, le tri à bulles bidirectionnel) est probablement idéal pour la plupart des listes triées, bien que je parie qu'un tri en peigne modifié (avec une taille d'écart initiale beaucoup plus faible) serait un peu plus rapide lorsque la liste n'était pas. t tout aussi parfaitement trié. Le tri au peigne se dégrade en un tri à bulles.
bien cela dépend du cas d'utilisation. Si vous savez quels éléments sont modifiés, supprimer et insérer sera le meilleur des cas en ce qui me concerne.
Ce test d'efficacité de l'algorithme «en ce qui me concerne» a égayé ma journée :) Être sérieux, cependant, en écrivant «supprimer et insérer» vouliez-vous dire Tri par insertion (qui était déjà mentionné dans les réponses précédentes), ou offrez-vous un nouveau type d'algorithme? Si tel est le cas, veuillez développer votre réponse.
yoniLavi
0
Le tri à bulles est définitivement le gagnant Le prochain sur le radar serait le tri par insertion.
Je vous suggère de jeter un œil aux réponses disponibles avant de poster pour éviter les doublons.
angainor
-1
Éloignez-vous de QuickSort - c'est très inefficace pour les données pré-triées. Le tri par insertion gère presque bien les données triées en déplaçant le moins de valeurs possible.
Réponses:
Basé sur la méthode hautement scientifique de regarder des gifs animés, je dirais que les types d'insertion et de bulles sont de bons candidats.
la source
Seulement quelques articles => TRI D'INSERTION
Les articles sont pour la plupart déjà triés => TRI D'INSERTION
Préoccupé par les pires scénarios => HEAP SORT
Intéressé par un bon résultat moyen => QUICKSORT
Les objets sont tirés d'un univers dense => TRI BUCKET
Désir d'écrire le moins de code possible => TRI D'INSERTION
la source
Timsort
Timsort est "une fusion adaptative, stable et naturelle" avec "des performances surnaturelles sur de nombreux types de tableaux partiellement ordonnés (moins de comparaisons lg (N!) Nécessaires, et aussi peu que N-1)". Intégré à Python
sort()utilise cet algorithme depuis un certain temps, apparemment avec de bons résultats. Il est spécialement conçu pour détecter et tirer parti des sous-séquences partiellement triées dans l'entrée, qui se produisent souvent dans des ensembles de données réels. Il arrive souvent dans le monde réel que les comparaisons coûtent beaucoup plus cher que d'échanger des éléments dans une liste, car on n'échange généralement que des pointeurs, ce qui fait très souvent de timsort un excellent choix. Cependant, si vous savez que vos comparaisons sont toujours très bon marché (écrire un programme jouet pour trier des entiers 32 bits, par exemple), il existe d'autres algorithmes qui sont susceptibles de mieux fonctionner. Le moyen le plus simple de tirer parti du tri temporel est bien sûr d'utiliser Python, mais comme Python est open source, vous pourrez peut-être également emprunter le code. Sinon, la description ci-dessus contient plus que suffisamment de détails pour écrire votre propre implémentation.la source
lg(n!)comparaisons sur un tableau presque trié, jusqu'àO(n)! | @behrooz: Aucun tri de comparaison ne peut avoir un cas moyen supérieur àO(n log n)etlg(n!)estO(n log n). Le pire des cas de Timsort n'est donc asymptotiquement pas pire que celui de tout autre type de comparaison. De plus, son meilleur cas est meilleur ou égal à tout autre type de comparaison.Tri par insertion avec le comportement suivant:
kdans les emplacements1..n, vérifiez d'abord siel[k] >= el[k-1]. Si tel est le cas, passez à l'élément suivant. (Évidemment, sautez le premier élément.)1..k-1pour déterminer l'emplacement d'insertion, puis parcourez les éléments. (Vous ne pouvez le faire que sik>ToùTest une valeur de seuil; avec un petit,kc'est exagéré.)Cette méthode fait le moins de comparaisons.
la source
Essayez le tri introspectif. http://en.wikipedia.org/wiki/Introsort
Il est basé sur le tri rapide, mais il évite le pire des cas de comportement du tri rapide pour les listes presque triées.
L'astuce est que cet algorithme de tri détecte les cas où le tri rapide passe dans le mode le plus défavorable et passe au tri par tas ou par fusion. Les partitions presque triées sont détectées par une méthode de partition non naiive et les petites partitions sont gérées à l'aide du tri par insertion.
Vous obtenez le meilleur de tous les principaux algorithmes de tri pour le coût d'un code et d'une complexité accrus. Et vous pouvez être sûr que vous ne rencontrerez jamais le pire des cas, quelle que soit l'apparence de vos données.
Si vous êtes un programmeur C ++, vérifiez votre algorithme std :: sort. Il peut déjà utiliser un tri introspectif en interne.
la source
Splaysort est une méthode de tri obscure basée sur des arbres splay , un type d'arbre binaire adaptatif. Splaysort est bon non seulement pour les données partiellement triées, mais aussi pour les données partiellement triées inversement, ou en fait pour toutes les données qui ont un ordre préexistant. C'est O (nlogn) dans le cas général, et O (n) dans le cas où les données sont triées d'une manière ou d'une autre (avant, arrière, orgue, etc.).
Son grand avantage par rapport au tri par insertion est qu'il ne revient pas au comportement O (n ^ 2) lorsque les données ne sont pas du tout triées, vous n'avez donc pas besoin d'être absolument sûr que les données sont partiellement triées avant de les utiliser .
Son inconvénient est la surcharge d'espace supplémentaire de la structure d'arbre splay dont elle a besoin, ainsi que le temps nécessaire pour construire et détruire l'arbre splay. Mais en fonction de la taille des données et de la quantité de pré-tri que vous attendez, la surcharge peut en valoir la peine pour l'augmentation de la vitesse.
Un article sur splaysort a été publié dans Software - Practice & Experience.
la source
insertion ou tri shell!
la source
Le tri en douceur de Dijkstra est un excellent tri sur les données déjà triées. C'est une variante heapsort qui s'exécute dans le pire des cas O (n lg n) et dans le meilleur des cas O (n). J'ai écrit une analyse de l'algorithme, au cas où vous seriez curieux de savoir comment cela fonctionne.
Le tri de fusion naturel est un autre très bon pour cela - c'est une variante de tri de fusion ascendante qui fonctionne en traitant l'entrée comme la concaténation de plusieurs plages triées différentes, puis en utilisant l'algorithme de fusion pour les joindre. Vous répétez ce processus jusqu'à ce que toute la plage d'entrée soit triée. Cela s'exécute dans le temps O (n) si les données sont déjà triées et dans le pire des cas O (n lg n). C'est très élégant, bien qu'en pratique ce ne soit pas aussi bon que d'autres types adaptatifs comme Timsort ou smoothsort.
la source
Si les éléments sont déjà triés ou s'il n'y a que peu d'éléments, ce serait un cas d'utilisation parfait pour le tri par insertion!
la source
Le tri par insertion prend du temps O (n + le nombre d'inversions).
Une inversion est une paire
(i, j)telle quei < j && a[i] > a[j]. Autrement dit, une paire dans le désordre.Une mesure de «presque triés» est le nombre d'inversions - on pourrait prendre «des données presque triées» pour signifier des données avec peu d'inversions. Si l'on sait que le nombre d'inversions est linéaire (par exemple, vous venez d'ajouter des éléments O (1) à une liste triée), le tri par insertion prend O (n) temps.
la source
Comme tout le monde l'a dit, faites attention au tri rapide naïf - qui peut avoir des performances O (N ^ 2) sur des données triées ou presque triées. Néanmoins, avec un algorithme approprié pour le choix du pivot (aléatoire ou médian sur trois - voir Choisir un pivot pour Quicksort ), Quicksort fonctionnera toujours correctement.
En général, la difficulté de choisir des algorithmes tels que le tri par insertion est de décider quand les données sont suffisamment désordonnées pour que Quicksort soit vraiment plus rapide.
la source
Je ne vais pas prétendre avoir toutes les réponses ici, car je pense que pour obtenir les réponses réelles, il faudra peut-être coder les algorithmes et les profiler par rapport à des échantillons de données représentatifs. Mais j'ai réfléchi à cette question toute la soirée, et voici ce qui m'est arrivé jusqu'à présent, et quelques suppositions sur ce qui fonctionne le mieux où.
Soit N le nombre total d'articles, M le nombre en désordre.
Le tri à bulles devra faire quelque chose comme 2 * M + 1 passes à travers tous les N éléments. Si M est très petit (0, 1, 2?), Je pense que ce sera très difficile à battre.
Si M est petit (disons moins que log N), le tri par insertion aura de bonnes performances moyennes. Cependant, à moins qu'il n'y ait un truc que je ne vois pas, il aura de très mauvaises performances dans le pire des cas. (Non? Si le dernier élément de la commande vient en premier, vous devez insérer chaque élément, pour autant que je puisse voir, ce qui va tuer les performances.) Je suppose qu'il existe un algorithme de tri plus fiable pour cela cas, mais je ne sais pas ce que c'est.
Si M est plus grand (disons égal ou grand que log N), le tri introspectif est presque certainement le meilleur.
Exception à tout cela: si vous savez réellement à l'avance quels éléments ne sont pas triés, alors votre meilleur pari sera de retirer ces éléments, de les trier en utilisant un tri introspectif et de fusionner les deux listes triées en une seule liste triée. Si vous pouviez rapidement déterminer quels articles sont en panne, ce serait également une bonne solution générale - mais je n'ai pas été en mesure de trouver un moyen simple de le faire.
Réflexions supplémentaires (pendant la nuit): Si M + 1 <N / M, vous pouvez parcourir la liste à la recherche d'une série de N / M dans une ligne qui est triée, puis étendre cette course dans les deux sens pour trouver le hors de -Items commandés. Cela prendra au plus 2N comparaisons. Vous pouvez ensuite trier les éléments non triés et effectuer une fusion triée sur les deux listes. Les comparaisons totales devraient être inférieures à quelque chose comme 4N + M log2 (M), ce qui va battre toute routine de tri non spécialisée, je pense. (Encore plus de réflexion: c'est plus délicat que je ne le pensais, mais je pense toujours que c'est raisonnablement possible.)
Une autre interprétation de la question est qu'il peut y avoir de nombreux articles dans le désordre, mais ils sont très proches de l'endroit où ils devraient être dans la liste. (Imaginez commencer par une liste triée et échanger tous les autres éléments avec celui qui suit.) Dans ce cas, je pense que le tri à bulles fonctionne très bien - je pense que le nombre de passes sera proportionnel au plus éloigné d'un élément est. Le tri par insertion fonctionnera mal, car chaque élément hors service déclenchera une insertion. Je soupçonne que le tri introspectif ou quelque chose comme ça fonctionnera bien aussi.
la source
Si vous avez besoin d'une implémentation spécifique pour les algorithmes de tri, les structures de données ou tout ce qui a un lien avec ce qui précède, puis-je vous recommander l'excellent projet "Structures de données et algorithmes" sur CodePlex?
Il aura tout ce dont vous avez besoin sans réinventer la roue.
Juste mon petit grain de sel.
la source
Cette belle collection d'algorithmes de tri à cet effet dans les réponses, semble manquer de Gnome Sort , qui conviendrait également, et nécessite probablement le moins d'effort de mise en œuvre.
la source
Le tri par insertion est le meilleur des cas O (n) sur une entrée triée. Et c'est très proche sur les entrées principalement triées (mieux que le tri rapide).
la source
réfléchissez à Essayez Heap. Je crois que c'est le plus cohérent des types O (n lg n).
la source
Le tri à bulles (ou, plus sûr encore, le tri à bulles bidirectionnel) est probablement idéal pour la plupart des listes triées, bien que je parie qu'un tri en peigne modifié (avec une taille d'écart initiale beaucoup plus faible) serait un peu plus rapide lorsque la liste n'était pas. t tout aussi parfaitement trié. Le tri au peigne se dégrade en un tri à bulles.
la source
bien cela dépend du cas d'utilisation. Si vous savez quels éléments sont modifiés, supprimer et insérer sera le meilleur des cas en ce qui me concerne.
la source
Le tri à bulles est définitivement le gagnant Le prochain sur le radar serait le tri par insertion.
la source
Éloignez-vous de QuickSort - c'est très inefficace pour les données pré-triées. Le tri par insertion gère presque bien les données triées en déplaçant le moins de valeurs possible.
la source