Quand chaque algorithme de sorting est-il utilisé?

Quels sont les cas d’utilisation lorsqu’un algorithme de sorting particulier est préféré à d’autres – merge sort vs quick sort vs heap sort vs intro sort , etc.

Existe-t-il un guide recommandé pour leur utilisation en fonction de la taille, du type de structure de données, de la mémoire disponible et du cache, ainsi que des performances du processeur?

Tout d’abord, une définition, car elle est très importante: un sorting stable est celui qui garantit de ne pas réorganiser les éléments avec des clés identiques.

Recommandations:

Tri rapide: lorsque vous n’avez pas besoin d’un sorting stable et que les performances moyennes des cas importent plus que les performances les plus défavorables. Un sorting rapide est O (N log N) en moyenne, O (N ^ 2) dans le pire des cas. Une bonne implémentation utilise le stockage auxiliaire O (log N) sous forme d’espace de stack pour la récursivité.

Fusionner le sorting: Lorsque vous avez besoin d’un sorting stable, O (N log N), il s’agit de votre seule option. Le seul inconvénient est qu’il utilise un espace auxiliaire O (N) et a une constante légèrement plus grande qu’un sorting rapide. Il existe certains types de fusion sur place, mais ils ne sont pas tous stables ou pires que O (N log N). Même les constantes O (N log N) en place ont une constante tellement plus grande que les anciennes méthodes de fusion, qui sont plus des curiosités théoriques que des algorithmes utiles.

Tri du tas: Lorsque vous n’avez pas besoin d’un sorting stable et que vous vous souciez davantage des performances les plus défavorables que les performances moyennes des cas. Il est garanti qu’il s’agisse de O (N log N) et utilise un espace auxiliaire O (1), ce qui signifie que vous ne serez pas à court de tas ou d’espace de stack sur des entrées très volumineuses.

Introsort: Ceci est un sorting rapide qui passe à un sorting de tas après une certaine profondeur de récursion pour contourner le pire des cas O (N ^ 2). C’est presque toujours mieux qu’un simple sorting rapide, puisque vous obtenez le cas moyen d’un sorting rapide, avec des performances O (N log N) garanties. Probablement la seule raison d’utiliser un sorting de tas au lieu de cela est dans les systèmes fortement limités en mémoire où l’espace de stack O (log N) est pratiquement significatif.

Tri par insertion : lorsque N est garanti petit, y compris comme cas de base d’un sorting rapide ou d’un sorting par fusion. Bien que ce soit O (N ^ 2), il a une très petite constante et est un sorting stable.

Tri par bulles, sorting par sélection : Lorsque vous faites quelque chose de rapide et de sale et que, pour une raison quelconque, vous ne pouvez pas utiliser l’algorithme de sorting de la bibliothèque standard. Le seul avantage que présente le sorting par insertion est légèrement plus facile à mettre en œuvre.


Types sans comparaison: Dans certaines conditions assez limitées, il est possible de casser la barrière O (N log N) et de sortinger O (N). Voici quelques cas où cela vaut la peine d’essayer:

Tri par comptage: lorsque vous sortingez des nombres entiers limités.

Sort de base: lorsque log (N) est significativement plus grand que K, où K est le nombre de chiffres de base.

Type de seau: Lorsque vous pouvez garantir que votre saisie est dissortingbuée à peu près uniformément.

Un ensemble d’animations pour différents types de données et d’algorithmes peut être trouvé sur sorting-algorithms.com

Quicksort est généralement le plus rapide en moyenne, mais il a des comportements très mauvais. Donc, si vous devez garantir qu’aucune mauvaise donnée ne vous donne O(N^2) , vous devriez l’éviter.

Merge-sort utilise de la mémoire supplémentaire, mais convient particulièrement au sorting externe (c.-à-d. Des fichiers volumineux qui ne rentrent pas dans la mémoire).

Heap-sort peut sortinger sur place et ne présente pas le comportement quadratique le plus défavorable, mais est en moyenne plus lent que le sorting rapide dans la plupart des cas.

Lorsque seuls des entiers dans une plage restreinte sont impliqués, vous pouvez utiliser une sorte de sorting de base pour le rendre très rapide.

Dans 99% des cas, vous serez d’accord avec les types de bibliothèques, qui sont généralement basés sur le sorting rapide.

La page Wikipedia sur les algorithmes de sorting a un excellent tableau de comparaison.

http://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms

Ce que les liens fournis avec les comparaisons / animations ne prennent pas en compte, c’est lorsque la quantité de données dépasse la mémoire disponible – le nombre de passages sur les données, c.-à-d. Si vous devez le faire, lisez le “sorting externe” qui couvre généralement des variantes de sorting de fusion et de tas.

http://corte.si/posts/code/visualisingsorting/index.html et http://corte.si/posts/code/timsort/index.html ont également des images sympas comparant différents algorithmes de sorting.

@dsimcha a écrit: Tri par comptage: lorsque vous sortingez des nombres entiers limités

Je changerais cela pour:

Tri par comptage: Lorsque vous sortingez des entiers positifs (0 – Integer.MAX_VALUE-2 en raison du casier).

Vous pouvez toujours obtenir les valeurs max et min comme une heuristique d’efficacité en temps linéaire.
Aussi, vous avez besoin d’au moins n espace supplémentaire pour le tableau intermédiaire et il est évidemment stable.

 /** * Some VMs reserve some header words in an array. * Attempts to allocate larger arrays may result in * OutOfMemoryError: Requested array size exceeds VM limit */ private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; 

(même si cela permet effectivement MAX_VALUE-2), voir: Les baies Java ont-elles une taille maximale?

Je voudrais aussi expliquer que la complexité de sorting par radix est O (wn) pour n clés qui sont des entiers de taille de mot w. Parfois, w est présenté comme une constante, ce qui rendrait le sorting de base plus correct (n suffisamment grand) que les meilleurs algorithmes de sorting basés sur des comparaisons, qui effectuent tous des comparaisons O (n log n) pour sortinger n clés. Cependant, en général, w ne peut pas être considéré comme une constante: si toutes les n clés sont distinctes, alors w doit être au moins log n pour qu’une machine à access aléatoire puisse les stocker en mémoire, ce qui donne au mieux une complexité temporelle O (n log n). (de wikipedia)