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).