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

Heapsort est garanti O(N log N), ce qui est bien mieux que le pire cas de Quicksort. Heapsort n'a pas besoin de plus de mémoire pour un autre tableau pour mettre les données ordonnées comme c'est le cas pour Mergesort. Alors pourquoi les applications commerciales s'en tiennent-elles à Quicksort ? Qu'est-ce que Quicksort a de si spécial par rapport à d'autres implémentations ?

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

Le secret de Quicksort est le suivant : Il n'effectue pratiquement pas de permutations inutiles d'éléments. La permutation prend du temps.

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

Avec Mergesort, c'est encore pire. Vous allez écrire 100% des éléments dans un autre tableau et les réécrire dans le tableau d'origine, 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 ordonnées, vous n'échangez presque rien ! Bien qu'il y ait beaucoup d'agitation autour du pire 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 à partir de l'élément intermédiaire entre le premier, le dernier et le milieu du tableau, cela suffit à éviter le pire des cas.

Ce qui est supérieur dans le Quicksort, ce 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. Dans le cas moyen, vous échangez une partie des éléments, mais pas tous les éléments, comme dans Heapsort et Mergesort. C'est ce qui permet à Quicksort d'être le plus rapide. Moins d'échanges, plus de vitesse.

L'implémentation ci-dessous en C# sur mon ordinateur, en mode release, bat Array.Sort de 3 secondes avec un pivot moyen et de 2 secondes avec un pivot amélioré (oui, il y a un surcoût 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 2

Ce document présente une certaine analyse.

Également, d'après Wikipédia :

T quicksort est le heapsort. Heapsort est généralement un peu plus lent que le quicksort, mais dans le pire des cas, le temps d'exécution est toujours de Θ(nlogn). Le quicksort est généralement plus rapide, bien qu'il reste la possibilité d'une performance dans le pire des cas sauf dans la variante introsort, qui passe au tri sélectif lorsqu'un mauvais cas est détecté. est détecté. Si l'on sait à l'avance que le tri sélectif sera nécessaire nécessaire, l'utiliser directement sera plus rapide que d'attendre qu'introsort basculer vers lui.

Answer 3

Dans la plupart des situations, le fait d'avoir un tri rapide ou un peu plus rapide n'a pas d'importance... vous ne voulez simplement pas qu'il devienne occasionnellement trop 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.

Dans les cas où la vitesse maximale est souhaitée dans la plupart des cas, QuickSort peut être préféré à HeapSort, mais ni l'un ni l'autre n'est forcément la bonne solution. Pour les situations où la vitesse est critique, il convient d'examiner attentivement les détails de la situation. Par exemple, dans certains de mes codes à vitesse critique, il est très fréquent que les données soient déjà triées ou presque triées (il s'agit d'indexer plusieurs champs liés qui souvent montent et descendent ensemble OU montent et descendent à l'opposé l'un de l'autre, donc une fois que vous avez trié l'un d'entre eux, les autres sont soit triés, soit triés à l'envers ou presque... l'un ou l'autre de ces cas peut tuer QuickSort). Dans ce cas, je n'ai implémenté ni l'un ni l'autre... à la place, j'ai implémenté le SmoothSort de Dijkstra... une variante du HeapSort qui est O(N) lorsqu'il est déjà trié ou presque trié... ce n'est pas très élégant, ni très facile à comprendre, mais c'est rapide... lire http://www.cs.utexas.edu/users/EWD/ewd07xx/EWD796a.PDF si vous voulez quelque chose d'un peu plus difficile à coder.

Answer 4

Les hybrides Quicksort-Heapsort in-place sont également très intéressants, car la plupart d'entre eux ne nécessitent que n*log n comparaisons dans le pire des cas (ils sont optimaux en ce qui concerne le premier terme de l'asymptotique, et évitent donc les pires scénarios de Quicksort), O(log n) espace supplémentaire et ils préservent au moins "la moitié" du bon comportement de Quicksort en ce qui concerne un ensemble de données déjà ordonnées. 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 de sqrt(n) éléments (ceci peut être réalisé en 24 comparaisons sqrt(n) au maximum grâce à l'algorithme de Tarjan&co, ou en 5 comparaisons sqrt(n) grâce à l'algorithme de l'usine-araignée de Schonhage, beaucoup plus alambiqué) ;
• Divisez votre tableau en deux parties, comme dans la première étape du tri sélectif ;
• Il s'agit d'encapsuler la plus petite partie et d'utiliser O(log n) bits supplémentaires pour coder un tas dans lequel chaque enfant de gauche a une valeur supérieure à celle de son frère ou de sa sœur ;
• Extraire récursivement la racine du tas, passer au crible 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é prélevé dans l'autre partie du tableau ;
• Recur sur la partie non ordonnée restante du tableau (si p est choisi comme médiane exacte, il n'y a pas de récursion du tout).

Answer 5

Heapsort a l'avantage d'avoir le pire cas d'exécution de O(n*log(n)) Ainsi, dans les cas où le tri sélectif risque d'être peu performant (généralement des ensembles de données triées), il est préférable d'opter pour le tri sélectif.