Quicksort vs Heapsort

Le tri rapide et le tri en tas effectuent le tri sur place. Ce qui est mieux? Quelles sont les applications et les cas dans lesquels l'un ou l'autre est préféré?

Cet article a une analyse.

Aussi, de Wikipedia:

Le concurrent le plus direct du tri rapide est le tri en tas. Heapsort est généralement un peu plus lent que quicksort, mais le temps d'exécution le plus défavorable est toujours Θ (nlogn). Le tri rapide est généralement plus rapide, bien qu'il reste la possibilité d'obtenir les pires performances, sauf dans la variante introsort, qui passe au tri en tas lorsqu'un mauvais cas est détecté. Si l'on sait à l'avance que le tri en tas sera nécessaire, l'utiliser directement sera plus rapide que d'attendre que l'introsort y passe.

Heapsort est O (N log N) garanti, ce qui est bien mieux que le pire des cas dans Quicksort. Heapsort n'a pas besoin de plus de mémoire pour un autre tableau afin de placer les données ordonnées comme le requiert Mergesort. Alors pourquoi les applications commerciales restent-elles avec Quicksort? Qu'est-ce que Quicksort a de si spécial par rapport aux autres implémentations?

J'ai testé les algorithmes moi-même et j'ai vu que Quicksort a vraiment quelque chose de spécial. Il s'exécute rapidement, beaucoup plus rapidement que les algorithmes Heap and Merge.

Le secret de Quicksort est: il n'effectue presque pas de permutations d'éléments inutiles. Le swap prend du temps.

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

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

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

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

L'implémentation ci-dessous en C # sur mon ordinateur, fonctionnant en mode release, bat Array.Sort de 3 secondes avec le pivot central et de 2 secondes avec un pivot amélioré (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);
}

Dans la plupart des situations, avoir rapide ou un peu plus rapide n'est pas pertinent ... vous ne voulez tout simplement jamais que cela devienne parfois lent. Bien que vous puissiez modifier QuickSort pour éviter les situations de lenteur, vous perdez l'élégance du QuickSort de base. Donc, pour la plupart des choses, je préfère HeapSort ... vous pouvez l'implémenter dans toute son élégance simple et ne jamais obtenir un tri lent.

Pour les situations où vous voulez une vitesse maximale dans la plupart des cas, QuickSort peut être préféré à HeapSort, mais ni l'un ni l'autre ne peut être la bonne réponse. Pour les situations où la vitesse est critique, il vaut la peine d'examiner de près les détails de la situation. Par exemple, dans certains de mes codes critiques pour la vitesse, il est très courant que les données soient déjà triées ou presque triées (il indexe plusieurs champs connexes qui se déplacent souvent de haut en bas ensemble OU se déplacent de haut en bas en face de l'autre, donc une fois que vous avez trié par un, les autres sont soit triés, soit triés par ordre inverse, soit fermés ... ce qui peut tuer QuickSort). Pour ce cas, je n'ai implémenté ni l'un ni l'autre ... à la place, j'ai implémenté SmoothSort de Dijkstra ... une variante HeapSort qui est O (N) lorsqu'elle est déjà triée ou presque triée ... ce n'est pas si élégant, pas trop facile à comprendre, mais vite ... lirehttp://www.cs.utexas.edu/users/EWD/ewd07xx/EWD796a.PDF si vous voulez quelque chose d'un peu plus difficile à coder.

Les hybrides en place Quicksort-Heapsort sont également très intéressants, car la plupart d'entre eux n'ont besoin que de comparaisons n * log n dans le pire des cas (ils sont optimaux par rapport au premier terme des asymptotiques, ils évitent donc les pires scénarios. de Quicksort), O (log n) extra-space et ils préservent au moins "la moitié" du bon comportement de Quicksort par rapport à un ensemble de données déjà ordonné. Un algorithme extrêmement intéressant est présenté par Dikert et Weiss dans http://arxiv.org/pdf/1209.4214v1.pdf :

• Sélectionnez un pivot p comme médiane d'un échantillon aléatoire d'éléments sqrt (n) (cela peut être fait dans au plus 24 comparaisons sqrt (n) via l'algorithme de Tarjan & co, ou 5 comparaisons sqrt (n) via l'araignée beaucoup plus compliquée -algorithme d'usine de Schonhage);
• Partitionnez votre tableau en deux parties comme dans la première étape de Quicksort;
• Heapify la plus petite partie et utilisez O (log n) bits supplémentaires pour coder un tas dans lequel chaque enfant gauche a une valeur supérieure à son frère;
• Extraire récursivement la racine du tas, tamiser la lacune laissée par la racine jusqu'à ce qu'elle atteigne une feuille du tas, puis remplir la lacune avec un élément approprié pris de l'autre partie du tableau;
• Répéter sur la partie non ordonnée restante du tableau (si p est choisi comme médiane exacte, il n'y a aucune récursivité).

Comp. entre quick sortet merge sortpuisque les deux sont du type de tri sur place, il y a une différence entre le temps d'exécution du cas le plus mauvais du temps d'exécution du cas le plus mauvais pour le tri rapide est O(n^2)et celui du tri en tas, il est toujoursO(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 ans corrects. en moins de temps dépendra de la position de l'élément pivot que vous choisissez.

Donc un

Bon appel: les tailles de L et G sont chacune inférieures à 3s / 4

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

pour une petite quantité, nous pouvons opter pour le tri par insertion et pour une très grande quantité de données, pour un tri par tas.

Heapsort a l'avantage d'avoir le pire cas d'exécution de O (n * log (n)), donc dans les cas où le tri rapide est susceptible de mal fonctionner (la plupart des ensembles de données triés généralement), le tri rapide est de loin préférable.

Eh bien, si vous passez au niveau de l'architecture ... nous utilisons la structure des données de la file d'attente dans la mémoire cache.Ainsi, tout 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 toute longueur ... mais en tas sort (en utilisant un tableau), il peut arriver que le parent ne soit pas présent dans le sous-tableau disponible dans le cache et qu'il doive ensuite le mettre dans la mémoire cache ... ce qui prend du temps. C'est le tri rapide, c'est le meilleur !! 😀

Heapsort crée un tas, puis extrait à plusieurs reprises l'élément maximal. Son pire cas est O (n log n).

Mais si vous voyiez le pire des cas de tri rapide , qui est O (n2), vous vous rendriez compte que le tri rapide ne serait pas un bon choix pour les données volumineuses.

Donc, cela fait du tri une chose intéressante; Je pense que la raison pour laquelle tant d'algorithmes de tri existent aujourd'hui est parce qu'ils sont tous «meilleurs» à leur meilleur endroit. Par exemple, le tri à bulles peut effectuer un 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, j'ai pensé ajouter mes deux cents.

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 Big-O(n logn), ce qui est meilleur que celui de Quicksort Big-O(n^2)dans le pire des cas. Cependant, Heapsort 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 rapide est due à la 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 localisation de référence sont d'excellents candidats pour l'optimisation des performances. Le tri en tas, cependant, traite des sauts plus importants. Cela rend le tri rapide plus favorable pour les petites entrées.

Pour moi, il y a une différence très fondamentale entre heapsort et quicksort: ce dernier utilise une récursivité. Dans les algorithmes récursifs, le tas augmente avec le nombre de récursions. Cela n'a pas d'importance si n est petit, mais en ce moment je trie deux matrices avec n = 10 ^ 9 !!. Le programme prend près de 10 Go de RAM et toute mémoire supplémentaire obligera mon ordinateur à commencer à basculer vers la mémoire du disque virtuel. Mon disque est un disque RAM, mais le fait d'échanger dessus fait une énorme différence de vitesse . Donc, dans un statpack codé en C ++ qui inclut des matrices de dimensions ajustables, avec une taille inconnue à l'avance pour le programmeur, et un type de tri statistique non paramétrique, je préfère le tri par tas pour éviter les retards aux utilisations avec des matrices de très grandes données.

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

Je viens de comparer les implémentations de sélection, de tri rapide, de fusion et de tri par tas pour voir comment elles se comparent. La réponse est qu'ils ont tous leurs inconvénients.

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

Sélection - N ^ 2 - Ce n'est vraiment bon que pour moins de 20 éléments environ, alors c'est surpassé. À moins que vos données ne soient déjà triées, ou presque. N ^ 2 devient très lent très vite.

Rapide, d'après mon expérience, n'est pas toujours aussi rapide. Les bonus pour utiliser le tri rapide comme tri général sont cependant qu'il est raisonnablement rapide et stable. C'est aussi un algorithme en place, mais comme il est généralement implémenté de manière récursive, il prendra de l'espace supplémentaire dans la pile. Il se situe également quelque part entre O (n log n) et O (n ^ 2). Le timing de certains types semble le confirmer, en particulier lorsque les valeurs se situent dans une fourchette étroite. C'est beaucoup plus rapide que le tri par sélection sur 10 000 000 éléments, mais plus lent que la fusion ou le tas.

Le tri par fusion est garanti O (n log n) car 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 grands types peuvent faire exploser votre pile si vous ne faites pas attention à l'implémentation. Il existe des implémentations complexes de tri de fusion sur place, mais généralement, vous avez besoin d'un autre tableau dans chaque niveau pour fusionner vos valeurs. Si ces tableaux vivent sur la pile, vous pouvez rencontrer des problèmes.

Le tri du tas est max O (n log n), mais dans de nombreux cas, il est plus rapide, en fonction de la distance à laquelle vous devez déplacer vos valeurs vers le haut du tas de log n profond. Le tas peut facilement être implémenté sur place dans le tableau d'origine, il n'a donc pas besoin de mémoire supplémentaire, et il est itératif, donc ne vous inquiétez pas du débordement de pile lors de la récurrence. L' énorme inconvénient du tri en tas est qu'il ne s'agit pas d'un tri stable, ce qui signifie qu'il est juste si vous en avez besoin.