Ordenação Rápida Vs Merge Sort

Por que a sorting rápida pode ser melhor que a de mesclagem?

Veja Quicksort na wikipedia :

Normalmente, o quicksort é significativamente mais rápido na prática do que outros algoritmos n (nlogn), porque seu loop interno pode ser implementado eficientemente na maioria das arquiteturas e, na maioria dos dados reais, é possível fazer escolhas de design que minimizam a probabilidade de exigir Tempo.

Observe que o requisito de memory muito baixa é uma grande vantagem também.

A sorting rápida geralmente é mais rápida que a de mesclagem quando os dados são armazenados na memory. No entanto, quando o dataset é enorme e é armazenado em dispositivos externos, como um disco rígido, o merge sort é o vencedor claro em termos de velocidade. Ele minimiza as leituras caras da unidade externa e também se presta bem à computação paralela.

Para Merge, o pior caso é O(n*log(n)) , para Quick sort: O(n 2 ) . Para outros casos (avg, melhor) ambos têm O(n*log(n)) . No entanto, a sorting rápida é uma constante de espaço, na qual a sorting de mesclagem depende da estrutura que você está classificando.

Veja esta comparação .

Você também pode ver visualmente .

Eu pessoalmente queria testar a diferença entre ordenação rápida e mesclagem eu mesmo e vi os tempos de execução para uma amostra de 1.000.000 de elementos.

A sorting rápida foi capaz de fazer isso em 156 milissegundos, enquanto a sorting Merge fez o mesmo em 247 milissegundos

Os dados de sorting rápida, no entanto, eram randoms e a sorting rápida funciona bem se os dados forem randoms, como não é o caso da sorting de mesclagem, ou seja, a sorting de mesclagem executa independentemente da mesma quando os dados são classificados ou não. Mas a ordenação por mesclagem requer um espaço extra completo e a sorting rápida não é um tipo no local

Eu escrevi programa de trabalho abrangente para eles serão imagens ilustrativas também.

Embora o quicksort seja muitas vezes uma escolha melhor do que o merge sort, há momentos em que o merge sort é uma opção melhor. O momento mais óbvio é quando é extremamente importante que seu algoritmo seja executado mais rápido que O (n ^ 2). O Quicksort é geralmente mais rápido do que isso, mas, dada a pior input teórica possível, ele pode ser executado em O (n ^ 2), que é pior do que a pior sorting de mesclagem possível.

O Quicksort também é mais complicado do que o mergesort, especialmente se você quiser escrever uma implementação realmente sólida e, portanto, se você deseja simplicidade e capacidade de manutenção, o merge sort se torna uma alternativa promissora com muito pouca perda de desempenho.

Além dos outros: Merge sort é muito eficiente para estruturas de dados imutáveis ​​como listas encadeadas e é, portanto, uma boa escolha para linguagens de programação (puramente) funcionais.

Um quicksort mal implementado pode ser um risco de segurança .

O Quicksort está no lugar. Você só precisa trocar posições de dados durante a function de particionamento. O Mergesort requer muito mais cópia de dados. Você precisa de outro armazenamento temporário (normalmente o mesmo tamanho do array de dados original) para a function Mesclar.

quicksort é assim chamado por uma razão,

destaques: ambos são tipos estáveis, (simplesmente um incômodo de implementação), então vamos apenas passar para as complexidades

é muito confuso com apenas as grandes notações sendo derramadas e “abusadas”, ambos têm uma complexidade média de 0 (nlogn),

mas merge sort é sempre 0 (nlogn), enquanto quicksort para partições ruins, isto é, partições distorcidas como 1 elemento element-10 (o que pode acontecer devido à lista ordenada ordenada ou invertida) pode levar a um 0 (n ^ 2) ..

.. e então nós randomizamos quicksort, onde escolhemos o pivot aleatoriamente e evitamos tal particionamento distorcido, anulando assim todo o cenário n ^ 2 de qualquer maneira mesmo para particionamento moderadamente distorcido como 3-4, temos um nlog (7/4) n , idealmente queremos 1-1 partion, assim, o todo 2 de O (nlog (2) n).

então é O (nlogn), quase sempre e ao contrário de merge sort as constantes escondidas sob a notação “big-oh” são melhores para quicksort do que para mergesort ..e ele não usa espaço extra como merge sort.

mas fazer o quicksort funcionar perfeitamente requer ajustes, reformulação, o quicksort oferece a oportunidade de ajustar …

A resposta seria um pouco tilt para quicksort wrt para alterações trazidas com DualPivotQuickSort para valores primitivos. É usado no JAVA 7 para ordenar em java.util.Arrays

 It is proved that for the Dual-Pivot Quicksort the average number of comparisons is 2*n*ln(n), the average number of swaps is 0.8*n*ln(n), whereas classical Quicksort algorithm has 2*n*ln(n) and 1*n*ln(n) respectively. Full mathematical proof see in attached proof.txt and proof_add.txt files. Theoretical results are also confirmed by experimental counting of the operations. 

Você pode encontrar a implicação JAVA7 aqui – http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7-b147/java/util/Arrays.java

Mais uma excelente leitura em DualPivotQuickSort – http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628

Não é verdade que o quicksort é melhor. Além disso, depende do que você quer dizer com melhor, consumo de memory ou velocidade.

Em termos de consumo de memory, no pior dos casos, o quicksort pode usar a memory n ^ 2 (ou seja, cada partição é de 1 a n-1), enquanto a sorting de mesclagem usa nlogn.

O acima segue em termos de velocidade.

O Quicksort está no lugar. Você precisa de muito pouca memory extra. Que é extremamente importante

Boa escolha de mediana torna ainda mais eficiente, mas até mesmo uma má escolha de quarentena mediana Theta (nlogn).