supériorité Quicksort sur Heap Trier

Question

Heap a Trier pire complexité de cas de O(nlogn) tout Quicksort a O(n^2). Mais les preuves emperical disent quicksort est supérieure. Pourquoi?

Answer 1

L'un des principaux facteurs est que quicksort a mieux localité de référence - la prochaine chose à accéder est généralement proche en mémoire à la chose que vous venez d'examiner. En revanche, heapsort sautille beaucoup plus. Puisque les choses qui sont proches les unes seront probablement mises en cache ensemble, quicksort a tendance à être plus rapide.

Cependant, de quicksort pire cas performance est nettement moins bonne que celle heapsort est. Parce que certaines applications critiques exigeront des garanties de performances de vitesse, heapsort est la bonne voie à suivre pour de tels cas.

Answer 2

Heapsort est O (N log N) guaranted, ce qui est beaucoup mieux que le pire des cas dans Quicksort. Heapsort ne ont 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

Voici une explication de couple:

http://www.cs.auckland.ac.nz/ logiciel / AlgAnim / qsort3.html

http://users.aims.ac.za/~mackay/ tri / sorting.html

Pour l'essentiel, même si le pire des cas pour le tri rapide est O (n ^ 2), il en moyenne des meilleures chances. : -)

Answer 4

La notation grand-O signifie que le temps nécessaire pour trier n éléments est limitée au-dessus par la fonction c*n*log(n), où c est un facteur constant non spécifié. Il n'y a aucune raison pour laquelle la c constante doit être la même pour quicksort et heapsort. Donc, la vraie question est: pourquoi vous attendez à être aussi rapide

Quicksort a toujours été un peu plus rapide que heapsort dans la pratique, mais la différence est devenue plus récemment depuis, comme mentionné précédemment, la localité d'accès à la mémoire est devenue si importante à la vitesse d'exécution.

Answer 5

complexité moyenne cas, et le fait que vous pouvez prendre des mesures simples pour réduire au minimum le risque de complexité dans le pire cas Quicksort (par exemple, sélectionnez le pivot comme une médiane de trois éléments plutôt que d'une seule position sélectionnée).