Pourquoi ne pas utiliser toujours le tri de tas

Question

L'algorithme de tri de type Heap Sort semble avoir une complexité de 0 (nlogn) dans le pire des cas, et utilise un espace O (1) pour l'opération de tri.

Cela semble meilleur que la plupart des algorithmes de tri. Alors, pourquoi n’utiliserait-on pas toujours Heap Sort comme algorithme de tri (et pourquoi les gens utilisent-ils des mécanismes de tri comme le tri par fusion ou le tri rapide)?

En outre, j'ai vu des gens utiliser le terme «instabilité» avec le type Heap. Qu'est-ce que cela implique?

Answer 1

Un tri stable maintient l'ordre relatif des éléments qui ont la même clé. Par exemple, imaginez que votre ensemble de données contient des enregistrements avec un id d'employé et un nom. La première commande est:

1, Jim
2, George
3, Jim
4, Sally
5, George

Vous souhaitez trier par nom. Un tri stable permettra d'organiser les éléments dans cet ordre:

2, George
5, George
1, Jim
3, Jim
4, Sally

Notez que les enregistrements en double pour "George" sont dans le même ordre relatif comme ils l'étaient dans la liste initiale. Même avec les deux "Jim" des dossiers.

Un tri instable pourrait arranger les éléments comme ceci:

5, George
2, George
1, Jim
3, Jim
4, Sally

Heapsort n'est pas stable parce que les opérations sur le tas peut changer l'ordre relatif des éléments égales. Pas tous les Quicksort implémentations sont stables. Cela dépend de comment mettre en œuvre le partitionnement.

Bien que Heapsort a un pire des cas, la complexité de l' O(n log(n)), qui ne raconte pas toute l'histoire. Dans le monde réel de la mise en œuvre, il y a constamment des facteurs que l'analyse théorique ne prend pas en compte. Dans le cas de Heapsort vs Quicksort, il s'avère qu'il existe des moyens (médiane de 5, par exemple) pour Quicksort pire des cas très rares en effet. En outre, le maintien d'un segment n'est pas libre.

Étant donné un tableau avec une distribution normale, Quicksort et Heapsort permettra à la fois de s'exécuter en O(n log(n)). Mais Quicksort s'exécutera plus rapidement en raison de sa constante des facteurs de plus petite taille que les facteurs constants pour Heapsort. Pour le dire simplement, le partitionnement est plus rapide que le maintien de la tas.

Answer 2

Le Tas de Tri a un pire des cas, la complexité de l' O(n log(n)). Pourtant, les études empiriques montrent que, généralement, la fonction de Tri Rapide (et d'autres algorithmes de tri) est considérablement plus rapide que le tas de tri, bien que sa pire des cas, la complexité est - O(n²) : http://www.cs.auckland.ac.nz/~jmor159/PLDS210/qsort3.html

Aussi, à partir de la fonction de tri rapide article sur Wikipedia:

La plupart concurrent direct de quicksort est heapsort. Heapsort le pire des cas, temps d'exécution est toujours en O(n log n). Mais, heapsort est supposé être en moyenne un peu plus lent en place de quicksort. C'est encore à l'étude et à la recherche, avec quelques publications indiquant le contraire.[13][14] Introsort est une variante de quicksort qui bascule à heapsort quand un mauvais cas est détecté pour éviter quicksort du pire cas de temps de fonctionnement. Si l'on sait à l'avance que heapsort va être nécessaire, en utilisant directement sera plus rapide que d'attendre pour introsort pour y passer.

Cependant, la fonction de tri rapide ne doit jamais être utilisé dans les applications qui exigent une garantie de temps de réponse!

Source sur Stackoverflow: Quicksort vs heapsort

Answer 3

Il n'y a pas de solution miracle ...

Juste pour mentionner un autre argument que je n'ai pas encore vu ici:

Si votre jeu de données est vraiment énorme et n'entre pas dans la mémoire, le tri par fusion fonctionne à merveille. Il est fréquemment utilisé dans des clusters où les jeux de données peuvent couvrir plusieurs centaines de machines.

Answer 4

Stable algorithmes de tri maintenir l'ordre relatif des enregistrements avec l'égalité des touches de

Certaines applications comme avoir ce genre de stabilité, la plupart ne se soucient pas, par exemple, Google est votre ami.

Comme pour vous, l'affirmation que "les gens utiliser le tri des mécanismes tels que la Fusion de tri ou tri Rapide" je parie que la plupart des gens utilisent tout ce qui est construit dans leur langue et ne pense pas à l'algorithme de tri de tout ce que beaucoup. Ceux qui roulent leurs propres avez probablement pas entendu parler de tas de tri (la dernière expérience personnelle).

La dernière et la plus grande raison est que pas tout le monde va vouloir un triées tas. Certaines personnes veulent la liste triée. Si la moyenne Joe du Programmeur patron dit "trier cette liste", et Joe dit: "Voici ce monceau, structure de données, vous n'avez jamais entendu parler de, boss!", Joe la prochaine révision de la performance n'est pas si grande.

Answer 5

Lorsque j'ai travaillé pour un court laps de temps sur Tandem Non-Stop ordinateurs dans le milieu des années 80, j'ai constaté que le système de base de la routine de tri a été HeapSort, précisément parce qu'il a donné la garantie NlogN performance. Je ne connais pas de personne qui l'avait aucune raison de l'utiliser, bien que, je ne sais donc pas comment cela a fonctionné dans la pratique. J'aime heapsort, mais également les inconvénients indiqué ci-dessus, j'ai entendu dire qu'il fait de la mauvaise utilisation moderne de souvenirs, car il rend l'accès à la mémoire de tous sur la place, tandis que quicksort et même de petits radix sortes en fin de brassage d'un relativement petit nombre de flux de lecture séquentielle et écrit - si les caches sont plus efficaces.