Quels sont les cas d'utilisation lorsqu'un algorithme de tri est préféré - merge sort vs quick sort vs heap sort vs introsort, etc?
Est-il un guide recommandé de les utiliser en fonction de la taille, le type de données de la structure, de la mémoire disponible et la mémoire cache et les performances du PROCESSEUR.
Tout d'abord, une définition, car c'est assez important: Un tri stable est celle qui est la garantie de ne pas réorganiser les éléments avec des clés identiques.
Recommandations:
Tri rapide: Lorsque vous n'avez pas besoin d'un tri stable et la moyenne des performances des questions plus pire des cas la performance. Un tri rapide est O(N log N) en moyenne, O(N^2) dans le pire des cas. Une bonne mise en œuvre utilise O(log N) auxiliaire de stockage sous la forme de l'espace de pile de récursion.
Fusion de tri: Lorsque vous avez besoin d'un stable, O(N log N) en quelque sorte, il s'agit de votre seule option. Les seuls inconvénients sont qu'il utilise O(N) auxiliaire de l'espace et est un peu plus grande constante qu'un tri rapide. Il y a quelques place de fusion de sortes, mais autant que je sache, ils sont tous soit pas stable ou pire que O(N log N). Même en O(N log N) dans le lieu sortes ont donc beaucoup plus constante que celle de la plaine de vieux fusion de sorte qu'ils sont plus théoriques curiosités que les algorithmes utiles.
Tas de tri: Lorsque vous n'avez pas besoin d'un tri stable et vous vous souciez plus des cas les pires performances que la moyenne des performances. C'est la garantie d'être en O(N log N), et utilise O(1) auxiliaire de l'espace, ce qui signifie que vous n'aurez pas exécuter inattendue de segment de mémoire ou d'espace de pile sur de très grandes entrées.
Introsort: C'est un tri rapide qui bascule sur un tas de tri après une certaine profondeur de récursion pour obtenir autour de la fonction de tri rapide est O(N^2) le pire des cas. C'est presque toujours de mieux qu'un bon vieux tri rapide, puisque vous obtenez la moyenne cas d'un tri rapide, avec des garanties de O(N log N) la performance. Probablement la seule raison d'utiliser un tas de tri au lieu de cela est sévèrement limitée par la mémoire des systèmes où O(log N) l'espace de pile est pratiquement significative.
Le tri par Insertion: Lorsque N est garanti pour être de petite taille, y compris le cas de base d'un tri rapide ou de fusion de tri. Bien que ce est O(N^2), il a une très faible constante et un tri stable.
Tri à bulles, tri de sélection: Lorsque vous êtes en train de faire quelque chose de rapide et sale, et pour une raison quelconque vous ne pouvez pas utiliser la bibliothèque standard de l'algorithme de tri. Le seul avantage de ces sur le tri par insertion est un peu plus facile à mettre en œuvre.
Non-comparaison sortes: dans certaines assez limité conditions, il est possible de rompre le O(N log N) barrière et de tri en O(N). Voici quelques cas où cela vaut la peine d'essayer:
Comptage tri: Lorsque vous effectuez le tri des entiers avec une gamme limitée.
Radix sort: Lors de log(N) est significativement supérieure à K, où K est le nombre de radix chiffres.
Seau de tri: Quand vous pouvez garantir que votre entrée est d'environ distribuées de manière uniforme.
Un ensemble d'animations pour différents types de données et algorithmes peuvent être trouvés à sorting-algorithms.com
Tri rapide est généralement le plus rapide en moyenne, mais elle a un assez méchant pour le pire des cas de comportements. Donc, si vous avez de garantir l'absence de mauvaises données vous donne O(N^2), vous devriez éviter.
Fusion-tri utilise plus de mémoire, mais est particulièrement adapté pour les externes de tri (c'est à dire de gros fichiers qui ne rentre pas dans la mémoire).
Tas de tri peut trier sur place et de ne pas avoir le pire des cas quadratique comportement, mais, en moyenne, est plus lent que quicksort dans la plupart des cas.
Où seuls les entiers dans une gamme restreinte sont impliqués, vous pouvez utiliser une sorte de tri radix, il est très rapide.
Dans 99% des cas, vous serez très bien avec la bibliothèque sortes, qui sont généralement basés sur le quicksort.
La page de Wikipedia sur les algorithmes de tri a un grand tableau de comparaison.
http://en.wikipedia.org/wiki/Sorting%5Falgorithm#Comparison%5Fof%5Falgorithms
Ce que les liens proposés pour les comparaisons/animations ne considèrent pas, c'est quand la quantité de données dépasse la mémoire disponible --- à quel point le nombre de passes sur les données, c'est à dire I/O-coûts, dominent le moment de l'exécution. Si vous avez besoin de le faire, lisez externe "tri" qui couvrent généralement des variantes de fusion - et des tas de sortes.
http://corte.si/posts/code/visualisingsorting/index.html et http://corte.si/posts/code/timsort/index.html ont également quelques belles images de la comparaison de différents algorithmes de tri.
Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
