Superioridade do Quicksort sobre o tipo de heap

Question

O tipo de heap tem a pior complexidade de O(nlogn) Enquanto o Quicksort tem O(n^2). Mas evidências emperais dizem que o Quicksort é superior. Por que é que?

Answer 1

Um dos principais fatores é que o Quicksort tem melhor localidade de referência - A próxima coisa a ser acessada é geralmente próxima na memória da coisa que você acabou de olhar. Por outro lado, Heapsort salta significativamente mais. Como as coisas que estão juntas provavelmente serão armazenadas em cache, o Quicksort tende a ser mais rápido.

No entanto, o choquesort pior caso O desempenho é significativamente pior que o de Heapsort. Como algumas aplicações críticas exigirão garantias de desempenho de velocidade, o HeapSort é o caminho certo para esses casos.

Answer 2

O Heapsort é o (n log n) garantido, o que é muito melhor que o pior caso no Quicksort. O HeapSort não precisa de mais memória para outra matriz para colocar dados ordenados, conforme necessário pelo Mergesort. Então, por que os aplicativos comerciais ficam com o Quicksort? O que o Quicksort tem que é tão especial sobre outras implementações?

Eu me testei os algoritmos e vi que o Quicksort tem algo especial. Ele funciona rápido, muito mais rápido que os algoritmos de heap e mesclagem.

O segredo do Quicksort é: quase não faz swaps de elementos desnecessários. A troca consome tempo.

Com o HeapSort, mesmo que todos os seus dados já estejam solicitados, você trocará 100% dos elementos para solicitar a matriz.

Com a mesclagem, é ainda pior. Você escreverá 100% dos elementos em outra matriz e escrevê -lo novamente no original, mesmo que os dados já sejam solicitados.

Com o Quicksort, você não troca o que já está ordenado. Se seus dados forem completamente encomendados, você troca quase nada! Embora haja muita confusão sobre o pior caso, uma pequena melhoria na escolha do pivô, qualquer outro que não seja o primeiro ou o último elemento da matriz, pode evitá -lo. Se você receber um pivô do elemento intermediário entre o primeiro, o elemento médio e o meio, é sujo evitar o pior caso.

O que é superior no Quicksort não é o pior caso, mas o melhor caso! No melhor caso, você faz o mesmo número de comparações, ok, mas você troca quase nada. No caso médio, você troca parte dos elementos, mas nem todos os elementos, como em Heapsort e Mergesort. É isso que dá ao Quicksort o melhor momento. Menos troca, mais velocidade.

A implementação abaixo no C# no meu computador, executando no modo de liberação, Beats Array.Sort por 3 segundos com pivô médio e por 2 segundos com pivô aprimorado (sim, há uma sobrecarga para obter um bom pivô).

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

Aqui estão algumas explicações:

http://www.cs.auckland.ac.nz/software/alganim/qsort3.html

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

Essencialmente, mesmo que o pior caso de classificação rápida seja O (n^2), em média, terá um desempenho melhor. :-)

Answer 4

A notação Big-O significa que o tempo necessário para classificar n itens é limitado acima pela função c*n*log(n), Onde c é algum fator constante não especificado. Não há razão para que a constante c deve ser o mesmo para quicksort e heapsort. Portanto, a verdadeira questão é: por que você espera que eles fossem igualmente rápidos?

Quicksort sempre foi um pouco mais rápido do que heapsort Na prática, mas a diferença tornou -se maior recentemente desde então, como mencionado anteriormente, a localidade do acesso à memória tornou -se tão importante para a velocidade de execução.

Answer 5

Complexidade de casos médios e o fato de você poder tomar medidas simples para minimizar o risco de pior complexidade no Quicksort (por exemplo, selecione o pivô como mediana de três elementos, em vez de uma única posição selecionada).