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

En termes simples >> HeapSort a un temps d'exécution garanti dans le pire des cas de "O(n log n)" par opposition à QuickSort qui a un temps d'exécution moyen de "O(n log n)". temps d'exécution ~moyen~ de QuickSort de "O(n log n)". QuickSort est généralement utilisé dans la pratique, car il est généralement plus rapide, mais HeapSort est utilisé pour le tri externe lorsque vous devez trier d'énormes fichiers qui ne tiennent pas dans la mémoire de votre de votre ordinateur.

Answer 2

Pour répondre à la question initiale et à certains des autres commentaires formulés ici :

Je viens de comparer les implémentations de la sélection, du tri rapide, de la fusion et du tri en tas pour voir comment elles se comparent les unes aux autres. La réponse est qu'elles ont toutes leurs inconvénients.

TL;DR : Quick est le meilleur tri à usage général (raisonnablement rapide, stable, et principalement in-place) Personnellement, je préfère le tri en tas, sauf si j'ai besoin d'un tri stable.

Sélection - N^2 - Elle n'est vraiment bonne que pour moins de 20 éléments environ, puis elle est surclassée. A moins que vos données ne soient déjà triées, ou très, très proches de l'être. N^2 devient très lent très rapidement.

D'après mon expérience, la rapidité n'est pas vraiment que rapide en permanence. L'avantage d'utiliser le tri rapide comme tri général est qu'il est raisonnablement rapide et stable. Il s'agit également d'un algorithme in-place, mais comme il est généralement implémenté de manière récursive, il occupera de l'espace supplémentaire sur la pile. Il se situe également entre O(n log n) et O(n^2). Le chronométrage de certains tris semble le confirmer, en particulier lorsque les valeurs se situent dans une fourchette étroite. Il est beaucoup plus rapide que le tri par sélection sur 10 000 000 d'éléments, mais plus lent que la fusion ou le tas.

Le tri par fusion est garanti O(n log n) puisque son tri ne dépend pas des données. Il fait simplement ce qu'il fait, quelles que soient les valeurs que vous lui avez données. Il est également stable, mais de très gros tris peuvent faire exploser votre pile si vous ne faites pas attention à l'implémentation. Il existe des implémentations complexes de tri par fusion sur place, mais en général vous avez besoin d'un autre tableau à chaque niveau pour fusionner vos valeurs. Si ces tableaux se trouvent sur la pile, vous pouvez rencontrer des problèmes.

Le tri en tas est au maximum O(n log n), mais dans de nombreux cas, il est plus rapide, en fonction de la distance à parcourir pour faire remonter les valeurs dans le tas d'une profondeur log n. Le tas peut facilement être implémenté sur place dans le tableau original, il ne nécessite donc pas de mémoire supplémentaire, et il est itératif, il n'y a donc pas de problème de débordement de pile lors de la récursivité. Le énorme L'inconvénient du tri par tas est qu'il n'est pas stable, ce qui signifie qu'il n'est pas possible de l'utiliser si vous en avez besoin.