Quicksort vs heapsort

Tanto o quicksort quanto o heapsort fazem a classificação no local. Qual é melhor? Quais são as aplicações e casos em que ambos são preferidos?

Este papel tem algumas análises.

Além disso, da Wikipedia:

O concorrente mais direto do quicksort é o heapsort. Heapsort é tipicamente um pouco mais lento do que quicksort, mas o pior caso de tempo de execução é sempre Θ (nlogn). O Quicksort geralmente é mais rápido, embora ainda haja a chance de desempenho no pior caso, exceto na variante introsort, que muda para o heapsort quando um caso ruim é detectado. Se for sabido com antecedência que o heapsort será necessário, usá-lo diretamente será mais rápido do que esperar que o introsort alterne para ele.

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

Eu mesmo testei os algoritmos e vi que o Quicksort tem algo realmente especial. Ele é executado rapidamente, muito mais rápido do que os algoritmos Heap e Merge.

O segredo do Quicksort é: ele quase não faz trocas de elementos desnecessárias. A troca é demorada.

Com o Heapsort, mesmo se todos os seus dados já estiverem ordenados, você vai trocar 100% dos elementos para ordenar o array.

Com o Mergesort, é ainda pior. Você vai escrever 100% dos elementos em outro array e escrever de volta no original, mesmo se os dados já estiverem ordenados.

Com Quicksort você não troca o que já foi pedido. Se seus dados estiverem completamente ordenados, você não troca quase nada! Embora haja muita confusão sobre o pior caso, uma pequena melhoria na escolha do pivô, qualquer outra coisa que não seja obter o primeiro ou o último elemento do array, pode evitá-lo. Se você obtiver um pivô do elemento intermediário entre o primeiro, o último e o elemento do meio, é suficiente para evitar o pior caso.

O que é superior no Quicksort não é o pior caso, mas o melhor! Na melhor das hipóteses você faz o mesmo número de comparações, ok, mas você não troca quase nada. Na média dos casos, você troca parte dos elementos, mas não todos os elementos, como no Heapsort e no Mergesort. Isso é o que dá ao Quicksort o melhor tempo. Menos troca, mais velocidade.

A implementação abaixo em C # no meu computador, rodando no modo de lançamento, bate Array.Sort em 3 segundos com o pivô intermediário e em 2 segundos com o 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);
}

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

Para situações em que você deseja a velocidade máxima na maioria dos casos, QuickSort pode ser preferido em vez de HeapSort, mas nenhuma 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 dos meus códigos de velocidade crítica, é muito comum que os dados já estejam classificados ou quase classificados (é a indexação de vários campos relacionados que muitas vezes movem para cima e para baixo juntos OU movem para cima e para baixo opostos um ao outro, então, uma vez que você classifica por um, os outros são classificados ou classificados de forma reversa ou próximos ... qualquer um dos quais pode matar QuickSort). Para esse caso, eu não implementei nenhum ... em vez disso, implementei o SmoothSort de Dijkstra ... uma variante HeapSort que é O (N) quando já classificada ou quase classificada ... não é tão elegante, não é muito fácil de entender, mas rápido ... leiahttp://www.cs.utexas.edu/users/EWD/ewd07xx/EWD796a.PDF se quiser algo um pouco mais desafiador para codificar.

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

• Selecione um pivô p como a mediana de uma amostra aleatória de elementos sqrt (n) (isso pode ser feito em no máximo 24 comparações sqrt (n) através do algoritmo de Tarjan & co, ou 5 comparações sqrt (n) através da aranha muito mais complicada -algoritmo de fábrica de Schonhage);
• Particione seu array em duas partes como na primeira etapa do Quicksort;
• Heapify a menor parte e use O (log n) bits extras para codificar um heap em que cada filho à esquerda tem um valor maior do que seu irmão;
• Extraia recursivamente a raiz da pilha, peneire a lacuna deixada pela raiz até chegar a uma folha da pilha e, em seguida, preencha a lacuna com um elemento apropriado retirado da outra parte da matriz;
• Recorre sobre a parte não ordenada restante da matriz (se p for escolhido como a mediana exata, não haverá recursão alguma).

Comp. entre quick sorte merge sortuma vez que ambos são do tipo de classificação local, há uma diferença entre o tempo de execução do caso errado para classificação rápida O(n^2)e para classificação de heap ainda é O(n*log(n))e para uma quantidade média de dados a classificação rápida será mais útil. Uma vez que é um algoritmo aleatório, então a probabilidade de obter ans corretos. em menos tempo dependerá da posição do elemento pivô que você escolher.

Então um

Boa escolha: os tamanhos de L e G são cada um menores que 3s / 4

Má chamada: um de L e G tem tamanho maior que 3s / 4

para uma pequena quantidade, podemos ir para a classificação por inserção e para uma quantidade muito grande de dados ir para a classificação por heap.

O Heapsort tem a vantagem de ter um pior caso de execução de O (n * log (n)), portanto, nos casos em que o quicksort provavelmente terá um desempenho insatisfatório (geralmente conjuntos de dados classificados principalmente), o heapsort é o preferido.

Bem, se você for para o nível de arquitetura ... usamos a estrutura de dados da fila na memória cache. Então, o que quer que esteja disponível na fila será classificado. Como na classificação rápida, não temos nenhum problema em dividir a matriz em qualquer comprimento ... mas em heap sort (usando array) pode acontecer que o pai não esteja presente no sub array disponível no cache e então ele tem que trazê-lo para a memória cache ... o que é demorado. Esse quicksort é o melhor !! 😀

O Heapsort cria um heap e extrai repetidamente o item máximo. Seu pior caso é O (n log n).

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

Portanto, isso torna a classificação uma coisa interessante; Acredito que a razão de tantos algoritmos de classificação existirem hoje é porque todos eles são 'melhores' em seus melhores lugares. Por exemplo, a classificação por bolha pode realizar uma classificação rápida se os dados forem classificados. Ou, se sabemos algo sobre os itens a serem classificados, provavelmente podemos fazer melhor.

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

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

O motivo pelo qual o heapsort é mais lento na prática do que o quicksort é devido à melhor localidade de referência (" https://en.wikipedia.org/wiki/Locality_of_reference ") no quicksort, onde os elementos de dados estão em locais de armazenamento relativamente próximos. Os sistemas que exibem forte localidade de referência são ótimos candidatos para otimização de desempenho. A classificação de heap, no entanto, lida com saltos maiores. Isso torna o quicksort mais favorável para entradas menores.

Para mim, há uma diferença fundamental entre o heapsort e o quicksort: o último usa uma recursão. Em algoritmos recursivos, o heap aumenta com o número de recursões. Isso não importa se n for pequeno, mas agora estou classificando duas matrizes com n = 10 ^ 9 !!. O programa ocupa quase 10 GB de RAM e qualquer memória extra fará com que meu computador comece a trocar para memória de disco virtual. Meu disco é um disco RAM, mas mesmo assim a troca para ele faz uma grande diferença na velocidade . Portanto, em um statpack codificado em C ++ que inclui matrizes de dimensão ajustáveis, com tamanho desconhecido de antemão para o programador, e tipo de classificação estatística não paramétrica, prefiro o heapsort para evitar atrasos no uso com matrizes de dados muito grandes.

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

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

TL; DR: Quick é o melhor tipo de uso geral (razoavelmente rápido, estável e principalmente no local). Pessoalmente, prefiro o tipo heap, a menos que precise de um tipo estável.

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

Rápido, na minha experiência, não é verdade que a rápida o tempo todo. Os bônus por usar a classificação rápida como uma classificação geral são que ela é razoavelmente rápida e estável. É também um algoritmo local, mas como geralmente é implementado recursivamente, ele ocupará espaço de pilha adicional. Ele também fica em algum lugar entre O (n log n) e O (n ^ 2). O tempo em alguns tipos parece confirmar isso, especialmente quando os valores estão dentro de uma faixa estreita. É muito mais rápido do que a classificação por seleção em 10.000.000 de itens, mas mais lento do que a fusão ou a pilha.

A classificação por mesclagem é garantida O (n log n), pois sua classificação não depende dos dados. Ele simplesmente faz o que faz, independentemente dos valores que você atribuiu a ele. Também é estável, mas tipos muito grandes podem explodir sua pilha se você não tiver cuidado com a implementação. Existem algumas implementações de classificação de mesclagem complexas no local, mas geralmente você precisa de outro array em cada nível para mesclar seus valores. Se essas matrizes estiverem na pilha, você poderá ter problemas.

A classificação de heap é max O (n log n), mas em muitos casos é mais rápida, dependendo de quanto você precisa mover seus valores para cima no heap de log n profundo. O heap pode ser facilmente implementado no local no array original, portanto, não precisa de memória adicional e é iterativo, portanto, não se preocupe com o estouro de pilha durante a recorrência. A grande desvantagem da classificação de heap é que não é uma classificação estável, o que significa que está pronta se você precisar disso.