Quicksort vs heapsort

Question

O Quicksort e o HeapSort fazem classificação no local. Qual é melhor? Quais são as aplicações e os casos em que são preferidos?

Answer 1

Este papel tem alguma análise.

Além disso, da Wikipedia:

O concorrente mais direto do Quicksort é o HeapSort. O Heapsort é tipicamente um pouco mais lento que o Quicksort, mas o pior tempo de execução é sempre θ (nLogn). O Quicksort é geralmente mais rápido, embora ainda exista a chance de desempenho do pior dos casos, exceto na variante de introstort, que muda para o HeapSort quando um caso ruim é detectado. Se for conhecido com antecedência que o HeapSort será necessário, usá -lo diretamente será mais rápido do que esperar que o Introsort mude para ele.

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

Para a maioria das situações, ter um pouco mais rápido é irrelevante ... você simplesmente nunca quer que ocasionalmente fique lento. Embora você possa ajustar o Quicksort para evitar a maneira como as situações lentas, você perde a elegância do Quicksort básico. Então, para a maioria das coisas, eu prefiro o HeapSort ... você pode implementá -lo em sua elegância simples e nunca obter um tipo lento.

Para situações em que você deseja velocidade máxima na maioria dos casos, o QuickSort pode ser preferido em relação ao HeapSort, mas nenhum deles pode ser a resposta certa. Para situações críticas de velocidade, vale a pena examinar de perto os detalhes da situação. Por exemplo, em alguns do meu código crítico de velocidade, é muito comum que os dados já estejam classificados ou quase classificados (está indexando vários campos relacionados que geralmente se movem para cima e para baixo juntos ou para cima e para baixo opostos, Então, uma vez que você classifique por um, os outros são classificados ou derrotados ou fechados ... um dos quais pode matar o Quicksort). Para esse caso, eu não implementei também ... em vez disso, implementei o smoothsort de Dijkstra ... uma variante HeapSort que é O (n) quando já classificada ou quase derrotada ... não é tão elegante, não é muito fácil de entender, Mas rápido ... leia http://www.cs.utexas.edu/users/ewd/ewd07xx/ewd796a.pdf Se você quer algo um pouco mais desafiador para codificar.

Answer 4

Os híbridos do chão-heapsort no local também são realmente interessantes, já que a maioria deles só precisa de comparações n*log n no pior caso (eles são ótimos em relação ao primeiro mandato dos assintóticos, para que evitem os pior cenários de Quicksort), O (log n) Espaço extra e eles preservam pelo menos "meio" do bom comportamento do Quicksort em relação ao conjunto de dados já ordenados. Um algoritmo extremamente interessante é apresentado por Dikert e Weiss em http://arxiv.org/pdf/1209.4214v1.pdf:

• Selecione um pivô p como mediana de uma amostra aleatória de elementos SQRT (n) (isso pode ser feito no máximo 24 Sqrt (N) comparações através do algoritmo de Tarjan & Co, ou 5 sqrt (n) comparações através da aranha muito mais complicada -factorial algoritmo de Schonhage);
• Participe sua matriz em duas partes, como na primeira etapa do Quicksort;
• Heapify a menor parte e use bits extras O (log n) para codificar uma pilha na qual cada criança esquerda tem um valor maior que seu irmão;
• Extrair recursivamente a raiz da pilha, peneire a lacune deixada pela raiz até atingir uma folha da pilha e, em seguida, preencha o lacune com um elemento apropriado tirado da outra parte da matriz;
• Recorre sobre a parte não ordenada restante da matriz (se p for escolhida como a mediana exata, não há recursão).

Answer 5

Comp. entre quick sort e merge sort Como ambos são tipos de classificação no lugar, há uma diferença entre o tempo de funcionamento do Wrost, o tempo de execução do Wrost Case para classificar rápido O(n^2) E para o tipo de heap ainda é O(n*log(n)) E para uma quantidade média de dados rápidos de dados, será mais útil. Como é algoritmo randomizado, a probabilidade de obter ANS correta. Em menos tempo dependerá da posição do elemento pivô que você escolher.

Então a

Boa decisão: Os tamanhos de L e G são inferiores a 3s/4

Mad Call: Um de L e G tem tamanho maior que 3s/4

Para uma pequena quantidade, podemos optar por uma espécie de inserção e para uma quantidade muito grande de dados, vá para o tipo de pilha.

Answer 6

Bem, se você for ao nível da arquitetura ... usamos a estrutura de dados da fila na memória do cache. Então, o que está disponível na fila será classificado. classificar (usando a matriz), pode acontecer que o pai possa não estar presente na sub -matriz disponível no cache e, em seguida, deve trazê -lo na memória de cache ... que consome tempo. Isso é o choquesort é o melhor !! 😀

Answer 7

Heapsort Construa uma pilha e extrai repetidamente o item máximo. O pior caso é O (n log n).

Mas se você ver o pior caso de ordenação rápida, que é O (n2), você percebeu que a classificação rápida seria uma opção não tão boa para dados grandes.

Portanto, isso torna a classificação é uma coisa interessante; Acredito que a razão pela qual tantos algoritmos de classificação vivem hoje é porque todos eles são "melhores" em seus melhores lugares. Por exemplo, a classificação de bolhas pode executar uma classificação rápida se os dados forem classificados. Ou, se soubermos algo sobre os itens a serem classificados, provavelmente podemos fazer melhor.

Isso pode não responder diretamente à sua pergunta, pensei em adicionar meus dois centavos.

Answer 8

Heapsort tem o benefício de ter o pior caso de execução de O (n*log (n)) Portanto, nos casos em que o Quicksort provavelmente terá um desempenho ruim (principalmente conjuntos de dados classificados em geral) é muito preferido.

Answer 9

O tipo de pilha é uma aposta segura ao lidar com entradas muito grandes. A análise assintótica revela a ordem de crescimento de Heapsort no pior caso é Big-O(n logn), o que é melhor do que o de Quicksort Big-O(n^2) Como pior caso. No entanto, Heapsort é um pouco mais lento na prática na maioria das máquinas do que uma espécie rápida bem implementada. O Heapsort também não é um algoritmo de classificação estável.

A razão pela qual o heapsort é mais lento na prática do que o Quicksort se deve à melhor localidade da referência ("https://en.wikipedia.org/wiki/locality_of_reference") No QuickSort, onde os elementos de dados estão dentro de locais de armazenamento relativamente próximos. Os sistemas que exibem forte localidade de referência são ótimos candidatos à otimização de desempenho. Corrente de heap, no entanto, lida com saltos maiores. Isso torna o Quicksort mais favorável para insumos menores.

Answer 10

Para mim, há uma diferença muito fundamental entre Heapsort e Quicksort: o último usa uma recursão. Em algoritmos recursivos, o heap cresce com o número de recursões. Isso não importa se n é pequeno, mas agora estou classificando duas matrizes com n= 10^9 !!. O programa leva quase 10 GB de RAM e qualquer memória extra fará com que meu computador comece a trocar pela memória do disco virtual. Meu disco é um disco de RAM, mas ainda está trocando para ele fazer um enorme diferença de velocidade. Portanto, em um Statpack codificado em C ++ que inclui matrizes de dimensão ajustáveis, com tamanho desconhecido com antecedência ao programador e tipo de classificação estatística não paramétrica, prefiro o HeapSort para evitar atrasos a usar com matrizes de muito big data.

Answer 11

Para responder à pergunta original e abordar alguns dos outros comentários aqui:

Acabei de comparar implementações de seleção, rápida, mesclagem e classificação de heap para ver como eles se compararam. A resposta é que todos eles têm suas desvantagens.

TL; DR: Rápido é o melhor tipo de propósito geral (razoavelmente rápido, estável e principalmente no local) pessoalmente, prefiro o tipo de heap, a menos que precise de um tipo estável.

Seleção - n^2 - É realmente bom apenas para menos de 20 elementos, então é superado. A menos que seus dados já estejam classificados, ou muito, muito quase assim. N^2 fica muito lento muito rápido.

Rápido, na minha experiência, não é realmente este rápido o tempo todo. Os bônus por usar a classificação rápida como tipo geral, porém, são razoavelmente rápidos e estáveis. É também um algoritmo no local, mas, como geralmente é implementado recursivamente, ele ocupará um espaço de pilha adicional. Também cai em algum lugar entre o (n log n) e o (n^2). O tempo em alguns tipos parece confirmar isso, especialmente quando os valores se enquadram em uma faixa apertada. É muito mais rápido que a seleção em 10.000.000 de itens, mas mais lenta que a mesclagem ou a pilha.

A classificação da mesclagem é garantida o (n log n), pois seu tipo não depende de dados. Apenas faz o que faz, independentemente dos valores que você deu. Também é estável, mas tipos muito grandes podem explodir sua pilha se você não tomar cuidado com a implementação. Existem algumas implementações complexas de classificação de mesclagem no local, mas geralmente você precisa de outra matriz em cada nível para mesclar seus valores. Se essas matrizes vivem na pilha, você poderá encontrar problemas.

O tipo de heap é máximo de O (n log n), mas em muitos casos é mais rápido, dependendo de quão longe você deve mover seus valores para cima do log n Deep Heap. A pilha pode ser facilmente implementada no local na matriz original, para que não precise de memória adicional e é iterativa, portanto, não se preocupe com o excesso de pilha durante o recurso. o enorme A desvantagem da classificação da pilha é que não é um tipo estável, o que significa que está certo se você precisar disso.