Quicksort vs heapsort

Question

Quicksort et heapsort effectuent tous deux un tri sur place. Lequel est le meilleur ? Quelles sont les applications et les cas dans lesquels l'un ou l'autre est préférable ?

Answer 1

Comp. entre quick sort y merge sort Comme il s'agit dans les deux cas d'un type de tri en place, il y a une différence entre le temps d'exécution du tri rapide en cas de gel et le temps d'exécution du tri rapide en cas de gel. O(n^2) et pour le tri des tas, c'est toujours O(n*log(n)) et pour une quantité moyenne de données, le tri rapide sera plus utile. Comme il s'agit d'un algorithme aléatoire, la probabilité d'obtenir des réponses correctes en moins de temps dépend de la position de l'élément pivot que vous choisissez.

Ainsi, un

C'est une bonne idée : les tailles de L et G sont chacune inférieures à 3s/4

Mauvaise décision : l'un des L et G a une taille supérieure à 3s/4

Pour les petites quantités de données, nous pouvons opter pour le tri par insertion et pour les très grandes quantités de données, nous pouvons opter pour le tri en tas.

Answer 2

Selon moi, il existe une différence fondamentale entre le tri par tas et le tri sélectif : ce dernier utilise une récursion. Dans les algorithmes récursifs, le tas croît avec le nombre de récursions. Cela n'a pas d'importance si n est faible, mais pour l'instant je trie deux matrices avec n \=10^9 ! !. Le programme prend presque 10 GB de ram et toute mémoire supplémentaire fera que mon ordinateur commencera à swapper vers la mémoire du disque virtuel. Mon disque est un disque RAM, mais le fait de swapper vers lui fait un grande différence de vitesse . Ainsi, dans un statpack codé en C++ qui inclut des matrices de dimensions ajustables, dont la taille est inconnue à l'avance par le programmeur, et des tris statistiques non paramétriques, je préfère le heapsort pour éviter les retards dans l'utilisation de très grandes matrices de données.

Answer 3

Si vous allez au niveau de l'architecture... nous utilisons une structure de données de file d'attente dans la mémoire cache... donc ce qui est disponible dans la file d'attente sera trié... Comme dans le tri rapide, nous n'avons aucun problème à diviser le tableau en n'importe quelle longueur... mais dans le tri en tas (en utilisant le tableau) il peut arriver que le parent ne soit pas présent dans le sous-réseau disponible dans la mémoire cache et alors il doit l'amener dans la mémoire cache... ce qui prend beaucoup de temps. C'est ce que le tri sélectif a de mieux à offrir !

Answer 4

Héliportage construit un tas et extrait de manière répétée l'élément maximal. Dans le pire des cas, il est O(n log n).

Mais si vous voulez voir le pire cas de tri rapide qui est O(n2), vous aurez compris que le tri rapide n'est pas un très bon choix pour les données volumineuses.

Je pense que la raison pour laquelle tant d'algorithmes de tri existent aujourd'hui est qu'ils sont tous "meilleurs" à leur meilleur endroit. Par exemple, le tri à bulles peut surpasser le tri rapide si les données sont triées. Ou si nous savons quelque chose sur les éléments à trier, nous pouvons probablement faire mieux.

Cela ne répond peut-être pas directement à votre question, mais j'ai pensé ajouter mon grain de sel.

Answer 5

Le tri en tas est une valeur sûre lorsqu'il s'agit d'entrées très volumineuses. L'analyse asymptotique révèle que l'ordre de croissance de Heapsort dans le pire des cas est de Big-O(n logn) qui est meilleure que celle de Quicksort Big-O(n^2) dans le pire des cas. Cependant, Héliportage est un peu plus lent en pratique sur la plupart des machines qu'un tri rapide bien implémenté. Heapsort n'est pas non plus un algorithme de tri stable.

La raison pour laquelle le tri en tas est plus lent en pratique que le tri sélectif est due à la meilleure localité de référence (" https://en.wikipedia.org/wiki/Locality_of_reference ") dans le tri sélectif, où les éléments de données se trouvent dans des emplacements de stockage relativement proches. Les systèmes qui présentent une forte localité de référence sont d'excellents candidats pour l'optimisation des performances. Le tri en tas, quant à lui, traite des sauts plus importants. Le tri sélectif est donc plus favorable pour les entrées plus petites.