Quel algorithme de sorting fonctionne le mieux sur la plupart des données sortingées?

Basé sur la méthode hautement scientifique de regarder des gifs animés, je dirais que les sortes d’insertion et de bulles sont de bons candidats.

Seulement quelques articles => TRI D’INSERTION

Les articles sont pour la plupart déjà sortingés => TRI D’INSERTION

Préoccupé par les pires scénarios => HEAP SORT

Intéressé par un bon résultat moyen => QUICKSORT

Les articles sont tirés d’un univers dense => BUCKET SORT

Désir d’écrire le moins de code possible => INSERTION SORT

timsort

Timsort est “un fusible naturel adaptatif, stable, avec des performances surnaturelles sur de nombreux types de tableaux partiellement ordonnés (comparaisons inférieures à lg (N!) Et aussi peu que N-1)”. Sort () de Python a utilisé cet algorithme pendant un certain temps, apparemment avec de bons résultats. Il est spécifiquement conçu pour détecter et tirer parti des sous-séquences partiellement sortingées dans l’entrée, qui se produisent souvent dans des jeux de données réels. Dans le monde réel, il est fréquent que les comparaisons soient beaucoup plus coûteuses que l’échange d’éléments dans une liste, car on ne fait généralement que permuter des pointeurs, ce qui fait très souvent un excellent choix pour Timort. Cependant, si vous savez que vos comparaisons sont toujours très bon marché (écrire un programme jouet pour sortinger des entiers de 32 bits, par exemple), il existe d’autres algorithmes susceptibles d’être plus performants. La manière la plus simple de tirer parti de timsort est bien sûr d’utiliser Python, mais puisque Python est open source, vous pouvez également emprunter le code. Alternativement, la description ci-dessus contient suffisamment de détails pour écrire votre propre implémentation.

Tri d’insertion avec le comportement suivant:

1. Pour chaque élément k dans les emplacements 1..n , vérifiez d’abord si el[k] >= el[k-1] . Si oui, passez à l’élément suivant. (Évitez évidemment le premier élément.)
2. Si ce n’est pas le cas, utilisez la recherche binary dans les éléments 1..k-1 pour déterminer l’emplacement d’insertion, puis supprimez les éléments. (Vous pouvez le faire uniquement si k>T où T est une valeur de seuil; avec k petit c’est excessif.)

Cette méthode fait le moins de comparaisons.

Essayez le sorting introspectif. http://en.wikipedia.org/wiki/Introsort

Il est basé sur le sorting rapide, mais il évite le comportement le plus défavorable que le sorting rapide a pour les listes presque sortingées.

L’astuce consiste en ce que cet algorithme de sorting détecte les cas où le sorting rapide passe dans le pire des cas et passe en sorting ou en fusion. Les partitions presque sortingées sont détectées par une méthode de partition non naïve et les petites partitions sont gérées par un sorting par insertion.

Vous obtenez le meilleur de tous les principaux algorithmes de sorting pour un coût et une complexité accrus. Et vous pouvez être sûr que vous ne rencontrerez jamais les pires comportements, 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 sorting introspectif en interne.

Splaysort est une méthode de sorting obscure basée sur des arbres splay , un type d’arbre binary adaptatif. Splaysort est utile non seulement pour les données partiellement sortingées, mais également pour les données partiellement sortingées inversement, ou même pour toutes les données ayant 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 sortingées d’une certaine manière (avant, inverse, organ-pipe, etc.).

Son grand avantage par rapport au sorting par insertion est qu’il ne revient pas au comportement O (n ^ 2) lorsque les données ne sont pas sortingées du tout, vous n’avez donc pas besoin d’être absolument certain que les données sont partiellement sortingées avant de les utiliser. .

Son inconvénient réside dans l’espace supplémentaire nécessaire à la structure de l’arborescence splay, ainsi que dans le temps nécessaire à la création et à la destruction de l’arborescence. Mais en fonction de la taille des données et de la quantité de pré-sorting que vous prévoyez, la surcharge peut en valoir la peine pour l’augmentation de la vitesse.

Un article sur splaysort a été publié dans Software – Practice & Experience.

insertion ou sorting de coquille!

Le smoothsort de Dijkstra est un excellent sorting sur les données déjà sortingées. C’est une variante horticole qui s’exécute dans le pire des cas et dans O (n) meilleur cas. J’ai écrit une parsing de l’algorithme, au cas où vous seriez curieux de savoir comment cela fonctionne.

La fusion naturelle est une autre très bonne pour cela – il s’agit d’une variante de fusion de bas en haut qui traite l’entrée comme la concaténation de plusieurs plages sortingées différentes, puis utilise l’algorithme de fusion pour les réunir. Vous répétez ce processus jusqu’à ce que toute la plage d’entrée soit sortingée. Cela se passe en heure O (n) si les données sont déjà sortingées et le pire des cas (O (ng n)). C’est très élégant, bien que dans la pratique ce ne soit pas aussi bon que d’autres types adaptatifs comme Timsort ou smoothsort.

Le sorting 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] . C’est-à-dire une paire hors service.

Une mesure de «presque sortingé» est le nombre d’inversions – on pourrait prendre des «données presque sortingées» pour désigner des données avec peu d’inversions. Si l’on sait que le nombre d’inversions est linéaire (par exemple, vous venez d’append des éléments O (1) à une liste sortingée), le sorting par insertion prend O (n) le temps.

Si des éléments sont déjà sortingés ou s’il n’y a que peu d’éléments, ce serait un cas d’utilisation parfait pour le sorting par insertion!

Comme tout le monde l’a dit, faites attention aux Quicksort naïfs – qui peuvent avoir des performances O (N ^ 2) sur des données sortingées ou presque sortingées. Néanmoins, avec un algorithme approprié pour le choix du pivot (aléatoire ou médian-de-trois – voir Choisir un pivot pour Quicksort ), Quicksort fonctionnera toujours de manière sûre.

En général, la difficulté avec le choix d’algorithmes tels que le sorting par insertion réside dans le fait de décider si les données sont suffisamment hors d’usage pour que Quicksort soit réellement plus rapide.

Je ne vais pas prétendre avoir toutes les réponses ici, car je pense que pour obtenir les réponses, il faudra peut-être coder les algorithmes et les profiler en fonction d’é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’ici, et quelques suppositions sur ce qui fonctionne le mieux où.

Soit N le nombre total d’éléments, M le nombre hors d’ordre.

Le sorting à bulles devra faire quelque chose comme 2 * M + 1 passe à 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 sorting par insertion aura une excellente performance moyenne. Cependant, à moins d’une astuce que je ne vois pas, les performances seront très mauvaises. (Droite? Si le dernier élément de la commande vient en premier, vous devez insérer chaque élément, autant que je sache, ce qui va tuer la performance.) Je suppose qu’il existe un algorithme de sorting plus fiable pour cela. cas, mais je ne sais pas ce que c’est.

Si M est plus grand (disons égal ou supérieur au log N), le sorting introspectif est presque certainement le meilleur.

Exception à tout cela: si vous savez en fait à l’avance quels éléments ne sont pas sortingés, le mieux est de retirer ces éléments, de les sortinger par sorting introspectif et de fusionner les deux listes sortingées en une seule liste sortingée. Si vous pouviez déterminer rapidement quels articles sont en panne, ce serait également une bonne solution générale – mais je n’ai pas été capable de trouver un moyen simple de le faire.

Autres reflections (du jour au lendemain): Si M + 1

Une autre interprétation de la question est qu’il peut y avoir beaucoup d’articles hors d’ordre, mais ils sont très proches de leur emplacement dans la liste. (Imaginez que vous commenciez avec une liste sortingée et que vous échangez tous les autres objects avec celui qui vient après.) Dans ce cas, je pense que le sorting à bulles fonctionne très bien – je pense que le nombre de passes sera proportionnel au plus éloigné est. Le sorting par insertion fonctionnera mal, car chaque article en désordre déclenchera une insertion. Je suspecte un sorting introspectif ou quelque chose comme ça va bien fonctionner aussi.

Si vous avez besoin d’une implémentation spécifique pour le sorting des algorithmes, des structures de données ou tout ce qui a un lien avec ce qui précède, pourrais-je vous recommander l’excellent projet “Data Structures and Algorithms” sur CodePlex?

Il aura tout ce dont vous avez besoin sans réinventer la roue.

Juste mon petit grain de sel.

Cette belle collection d’algorithmes de sorting à cette fin dans les réponses semble manquer de Gnome Sort , qui conviendrait également, et nécessite probablement le moins d’effort d’implémentation.

Le sorting par insertion est le meilleur cas O (n) sur les entrées sortingées. Et il est très proche de la plupart des entrées sortingées (mieux que le sorting rapide).

Réfléchissez Essayez Heap. Je crois que c’est la plus cohérente des sortes O (ng n).

Le sorting à bulles (ou, plus sûr encore, le sorting à bulles bidirectionnel) est probablement idéal pour la plupart des listes sortingées, même si je parie qu’un type de peigne modifié (avec une taille d’écart initiale beaucoup plus faible) serait un peu plus rapide lorsque la liste est vide. t aussi parfaitement sortingés. Le sorting par peigne se dégrade en sorting à bulles.

eh bien cela dépend du cas d’utilisation. Si vous savez quels éléments sont modifiés, enlevez et insérez sera le meilleur cas pour moi.

Le sorting à bulles est définitivement le vainqueur Le suivant sur le radar serait le sorting par insertion.

Restez à l’écart de QuickSort – c’est très inefficace pour les données pré-sortingées. Le sorting par insertion gère bien les données sortingées en déplaçant le moins de valeurs possible.