Quicksort vs heapsort

Question

Les deux quicksort et heapsort faire le tri en place. Ce qui est mieux? Quelles sont les applications et les cas où est soit préféré?

Answer 1

Cet article a une analyse .

En outre, de Wikipedia:

  

Le concurrent le plus direct de   quicksort est heapsort. Heapsort est   généralement un peu plus lent que   quicksort, mais le pire cas en cours d'exécution   le temps est toujours Θ (nlogn). quicksort est   généralement plus rapide, mais il reste   la chance de pire performance de cas   sauf dans la variante de introsort, qui   interrupteurs à HeapSort quand un mauvais cas   est détecté. Si l'on sait à l'avance   que heapsort va être   nécessaire, utiliser directement sera   plus rapide que d'attendre introsort à   passer à elle.

Answer 2

Heapsort est O (N log N) guaranted, ce qui est beaucoup mieux que le pire des cas dans Quicksort. Heapsort n'a pas besoin de plus de mémoire pour un autre tableau pour mettre les données ordonnées comme il est nécessaire par Mergesort. Alors, pourquoi les applications comercial avec bâton de Quicksort? Ce qui a Quicksort qui est si spécial implémentations sur les autres?

Je l'ai testé les algorithmes moi-même et je l'ai vu que Quicksort a en effet quelque chose de spécial. Il court vite, beaucoup plus vite que Heap et algorithmes de fusion.

Le secret de Quicksort est: Il ne fait presque pas des swaps de ne éléments inutiles. Swap est consommatrice de temps.

Avec Heapsort, même si toutes vos données sont déjà commandés, vous allez échanger 100% des éléments pour commander le tableau.

Avec Mergesort, il est encore pire. Vous allez écrire 100% des éléments dans un autre tableau et d'écrire le dans l'original, même si les données sont déjà commandés.

Avec Quicksort vous n'échangez pas ce qui est déjà commandé. Si vos données sont complètement commandé, vous échangez presque rien! Bien qu'il y ait beaucoup de tracasser pour le pire des cas, un peu d'amélioration sur le choix de pivot, tout autre que d'obtenir le premier ou le dernier élément du tableau, peut l'éviter. Si vous obtenez un pivot de l'élément intermédiaire entre l'élément premier, et dernier milieu, il est sufisamment pour éviter le pire des cas.

Ce qui est supérieure à Quicksort n'est pas le pire des cas, mais le meilleur des cas! Dans le meilleur des cas que vous faites le même nombre de comparaisons, ok, mais vous échangez presque rien. Dans le cas moyen vous échangez une partie des éléments, mais pas tous les éléments, comme dans Heapsort et Mergesort. Voilà ce qui donne Quicksort le meilleur temps. Moins swap, plus de vitesse.

La mise en œuvre ci-dessous en C # sur mon ordinateur, en cours d'exécution sur le mode de libération, battements Array.Sort de 3 secondes avec le pivot du milieu et de 2 secondes avec un meilleur pivot (oui, il y a une surcharge pour obtenir un bon pivot).

static void Main(string[] args)
{
    int[] arrToSort = new int[100000000];
    var r = new Random();
    for (int i = 0; i < arrToSort.Length; i++) arrToSort[i] = r.Next(1, arrToSort.Length);

    Console.WriteLine("Press q to quick sort, s to Array.Sort");
    while (true)
    {
        var k = Console.ReadKey(true);
        if (k.KeyChar == 'q')
        {
            // quick sort
            Console.WriteLine("Beg quick sort at " + DateTime.Now.ToString("HH:mm:ss.ffffff"));
            QuickSort(arrToSort, 0, arrToSort.Length - 1);
            Console.WriteLine("End quick sort at " + DateTime.Now.ToString("HH:mm:ss.ffffff"));
            for (int i = 0; i < arrToSort.Length; i++) arrToSort[i] = r.Next(1, arrToSort.Length);
        }
        else if (k.KeyChar == 's')
        {
            Console.WriteLine("Beg Array.Sort at " + DateTime.Now.ToString("HH:mm:ss.ffffff"));
            Array.Sort(arrToSort);
            Console.WriteLine("End Array.Sort at " + DateTime.Now.ToString("HH:mm:ss.ffffff"));
            for (int i = 0; i < arrToSort.Length; i++) arrToSort[i] = r.Next(1, arrToSort.Length);
        }
    }
}

static public void QuickSort(int[] arr, int left, int right)
{
    int begin = left
        , end = right
        , pivot
        // get middle element pivot
        //= arr[(left + right) / 2]
        ;

    //improved pivot
    int middle = (left + right) / 2;
    int
        LM = arr[left].CompareTo(arr[middle])
        , MR = arr[middle].CompareTo(arr[right])
        , LR = arr[left].CompareTo(arr[right])
        ;
    if (-1 * LM == LR)
        pivot = arr[left];
    else
        if (MR == -1 * LR)
            pivot = arr[right];
        else
            pivot = arr[middle];
    do
    {
        while (arr[left] < pivot) left++;
        while (arr[right] > pivot) right--;

        if(left <= right)
        {
            int temp = arr[right];
            arr[right] = arr[left];
            arr[left] = temp;

            left++;
            right--;
        }
    } while (left <= right);

    if (left < end) QuickSort(arr, left, end);
    if (begin < right) QuickSort(arr, begin, right);
}

Answer 3

Pour la plupart des situations, ayant rapidement par rapport à un peu plus rapide est hors de propos ... vous voulez tout simplement jamais à l'occasion obtenir waayyy lent. Bien que vous pouvez modifier QuickSort pour éviter la façon dont les situations lentes, vous perdez l'élégance du QuickSort de base. Donc, pour la plupart des choses, je préfère HeapSort ... vous pouvez la mettre en œuvre dans son élégance pleine simple, et jamais une sorte lente.

Pour les situations où vous ne voulez la vitesse maximale dans la plupart des cas, QuickSort peut être préféré HeapSort, mais ne peut être la bonne réponse. Pour les situations de vitesse critique, il convient d'examiner de près les détails de la situation. Par exemple, dans certains de ma vitesse critique code, il est très fréquent que les données sont déjà triées ou presque triée (il indexe plusieurs domaines connexes qui, souvent, soit déplacer vers le haut et vers le bas ensemble ou se déplacent vers le haut et vers le bas en face de l'autre, donc une fois que vous triez par un, les autres sont soit classés ou inverse triés ou à proximité ... ou l'autre qui peut tuer QuickSort). Pour ce cas, je ne ... à la place mis en œuvre, je smoothsort Dijkstra mis en œuvre ... une variante de HeapSort qui est O (N) lorsque déjà triée ou quasi triés ... il est si élégant, pas trop facile à comprendre, mais vite ... lire http://www.cs.utexas.edu /users/EWD/ewd07xx/EWD796a.PDF si vous voulez quelque chose d'un peu plus difficile à coder.

Answer 4

Quicksort-HeapSort hybrides en place sont vraiment intéressant, aussi, puisque la plupart d'entre eux n'a besoin que n * log n comparaisons dans le pire des cas (ils sont optimaux par rapport au premier terme des asymptote, donc ils évitent le pire scénarios de -Cas Quicksort), O (log n) espace supplémentaire et ils conservent au moins « une moitié » du bon comportement de Quicksort par rapport à ensemble déjà ordonné des données. Un algorithme extrêmement intéressant est présenté par Dikert et Weiss dans http://arxiv.org/pdf/1209.4214v1. pdf :

• Sélectionner une p pivot que la médiane d'un échantillon aléatoire d'éléments sqrt (n) (cela peut être fait dans au plus 24 comparaisons de sqrt (n) par l'algorithme de Tarjan & co, ou 5 comparaisons sqrt (n) à travers le beaucoup plus alambiquée algorithme usine d'araignée de Schönhage);
• partitionner votre matrice en deux parties, comme dans la première étape de tri rapide;
• Heapify la plus petite partie et l'utilisation O (log n) bits supplémentaires pour coder un tas dans lequel chaque enfant gauche a une valeur supérieure à ses frères et soeurs;
• extrait de manière récursive la racine du tas, tamiser sur la gauche par la lacune racine jusqu'à ce qu'il atteigne une feuille du tas, puis remplissez le avec un élément lacune approprié a pris de l'autre partie du tableau;
• réapparaître au cours de la partie restante non-ordonnée de l'ensemble (si p est choisie comme la valeur médiane exacte, il n'y a pas du tout récursion).

Answer 5

Comp. entre quick sort et merge sort puisque les deux sont du type de mis en place le tri, il y a une différence entre le cas wrost durée de l'affaire de wrost durée pour le tri rapide est O(n^2) et tas trier est O(n*log(n)) encore et pour une quantité moyenne de données de tri rapide sera être plus utile. Comme il est algorithme aléatoire de sorte que la probabilité d'obtenir correcte ans. en moins de temps dépendra de la position de l'élément pivot de votre choix.

a

Bon appel: les tailles de L et G sont chacun moins de 3 secondes / 4

Bad appel: un des L et G a une taille supérieure à 3 s / 4

pour peu que nous pouvons aller pour le tri d'insertion et très grande quantité de données vont pour le tri en tas.

Answer 6

Eh bien, si vous allez au niveau de l'architecture ... nous utilisons la structure de données de file d'attente dans le cache memory.so ce qui est toujours disponible en file d'attente va se sorted.As dans une sorte rapide, nous avons aucun problème divisant le tableau dans une longueur ... mais dans une sorte tas (en utilisant un tableau), il peut arriver que le parent ne peut pas être présent dans le tableau de sous disponible dans le cache, puis il doit le mettre en mémoire cache ... qui prend du temps. C'est quicksort est le meilleur !!

Answer 7

Heapsort construit un tas, puis extrait à plusieurs reprises le point maximal. Son pire des cas est O (n log n).

Mais si vous verriez le pire des cas de href="http://en.wikipedia.org/wiki/Quicksort" rapide sorte, qui est O (n2 ), vous réalisé ce genre rapide serait pas si bon choix pour les grandes quantités de données.

Cela fait donc le tri est une chose intéressante; Je crois que la raison pour laquelle tant d'algorithmes de tri vivent aujourd'hui parce que tous sont « meilleur » à leurs meilleurs endroits. Par exemple, une sorte de bulle peut surperformer tri rapide si les données sont triées. Ou si nous savons quelque chose sur les éléments à trier alors probablement que nous pouvons faire mieux.

Cela peut ne pas répondre directement à votre question, je pense ajouter mes deux cents.

Answer 8

Heapsort a l'avantage d'avoir le pire des cas de fonctionnement de O (n * log (n)) dans des cas où quicksort est susceptible d'être peu performants (ensembles de données principalement triés généralement) heapsort est beaucoup préféré.

Answer 9

Heap est un pari sûr Trier lorsqu'ils traitent avec des entrées très grandes. l'analyse révèle asymptote ordre de croissance de Heapsort dans le pire des cas est Big-O(n logn), ce qui est mieux que la Big-O(n^2) de Quicksort comme le pire des cas. Cependant, Heapsort est un peu plus lent dans la pratique sur la plupart des machines qu'un tri rapide bien mis en œuvre. Heapsort est pas non plus un algorithme de tri stable.

La heapsort raison est plus lente dans la pratique que quicksort est due à une meilleure localité de référence ( " https: / /en.wikipedia.org/wiki/Locality_of_reference ") dans le tri rapide, 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. sorte Heap, cependant, traite des sauts plus importants. Cela rend quicksort plus favorable pour les entrées plus petites.

Answer 10

Pour moi, il y a une différence fondamentale entre heapsort et quicksort: celui-ci utilise un récursivité. Dans les algorithmes récursifs le tas augmente avec le nombre de récurrences. Cela n'a pas d'importance si n est petit, mais en ce moment je suis deux matrices de tri avec n = 10 ^ 9 !!. Le programme prend près de 10 Go de RAM et une mémoire supplémentaire fera mon ordinateur pour commencer à échanger à la mémoire de disque virtuel. Mon disque est un disque de RAM, mais toujours la permutation à lui faire une énorme différence vitesse . Ainsi, dans un statpack codé en C ++ qui comprend des matrices de dimension réglable, avec une taille inconnue à l'avance pour le programmeur, et type statistique non paramétrique de tri que je préfère le heapsort pour éviter les retards à des utilisations très grandes matrices de données.

Answer 11

Pour répondre à la question initiale et répondre à certaines des autres commentaires ici:

Je viens de comparais implémentations sélection, rapide, fusion et tri tas pour voir comment ils avaient empiler les uns contre les autres. La réponse est qu'ils ont tous leurs inconvénients.

TL; DR: Quick est le meilleur type d'usage général (raisonnablement rapide, stable, et surtout en place) Personnellement, je préfère tas sorte que si je besoin d'un tri stable.

Sélection - N ^ 2 - Il est vraiment seulement bon pour moins de 20 éléments ou plus, il est surclassé. À moins que vos données sont déjà triées, ou très, très près. N ^ 2 devient vraiment très rapide lent.

rapide, dans mon expérience, n'est pas réellement que rapide tout le temps. Les bonus pour l'utilisation de tri rapide comme une sorte générale sont cependant qu'il est assez rapide et il est stable. Il est aussi un algorithme, mais comme il est généralement mis en œuvre récursive, il prendra en place l'espace de pile supplémentaire. Il tombe aussi quelque part entre O (n log n) et O (n ^ 2). Timing sur certaines sortes semblent confirmer, en particulier lorsque les valeurs se situent dans une fourchette étroite. Il est beaucoup plus rapide que sorte de sélection sur 10.000.000 objets, mais plus lent que la fusion ou tas.

Fusionner O est garanti tri (n log n) depuis son genre ne dépend pas des données. Il fait exactement ce qu'il fait, peu importe ce que vous avez donné les valeurs que. Il est également stable, mais très grandes sortes peut souffler votre pile si vous n'êtes pas attention à la mise en œuvre. Il y a quelques complexes en place la fusion des implémentations de tri, mais en général vous avez besoin d'un autre tableau dans chaque niveau pour fusionner vos valeurs dans. Si ces tableaux vivent sur la pile, vous pouvez rencontrer des problèmes.

Heap tri est max O (n log n), mais dans de nombreux cas, est plus rapide, en fonction de la distance que vous devez déplacer vos valeurs le journal n tas profond. Le tas peut facilement être mis en œuvre en place dans le tableau original, donc il n'a pas besoin de la mémoire supplémentaire, et il est itérative, donc pas de soucis au sujet de débordement de la pile tout en récursion. énorme inconvénient de tas est sorte qu'il ne soit pas une sorte stable, ce qui signifie qu'il est juste si vous avez besoin que.