it-swarm-pt.tech

Por que o quicksort é melhor que o mergesort?

Fiz esta pergunta durante uma entrevista. Ambos são O(nlogn) e ainda assim a maioria das pessoas usa o Quicksort em vez do Mergesort. Por que é que?

339
Malik Daud Ahmad Khokhar

O Quicksort tem O (n2) runtime de pior caso e O (nregistron) tempo de execução médio do caso. No entanto, é melhor mesclar a classificação em muitos cenários, pois muitos fatores influenciam o tempo de execução de um algoritmo e, ao combiná-los, o quicksort vence.

Em particular, o tempo de execução frequentemente cotado de algoritmos de ordenação refere-se ao número de comparações ou ao número de trocas necessárias para realizar a ordenação dos dados. Essa é realmente uma boa medida de desempenho, especialmente porque é independente do design de hardware subjacente. No entanto, outras coisas - como localidade de referência (ou seja, podemos ler muitos elementos que provavelmente estão no cache?) - também desempenham um papel importante no hardware atual. Quicksort em particular requer pouco espaço adicional e exibe boa localidade de cache, e isso torna mais rápido do que mesclar a classificação em muitos casos.

Além disso, é muito fácil evitar o tempo de execução de pior caso do quicksortn2) quase inteiramente usando uma escolha apropriada do pivot - tal como escolher aleatoriamente (esta é uma excelente estratégia).

Na prática, muitas implementações modernas de quicksort (em particular std::sort) de libstdc ++ são na verdade introsort , cujo pior caso teórico é O (nregistron), igual a merge sort. Ele consegue isso limitando a profundidade de recursão e alternando para um algoritmo diferente ( heapsort ) uma vez que excede logn.

253
Konrad Rudolph

Como muitas pessoas notaram, o desempenho médio do caso para o quicksort é mais rápido que o do mergesort. Mas isso só é verdade se você estiver assumindo tempo constante para acessar qualquer parte da memória sob demanda.

Em RAM essa suposição geralmente não é tão ruim (nem sempre é verdade por causa dos caches, mas não é tão ruim). No entanto, se a sua estrutura de dados é grande o suficiente para viver no disco, o quicksort recebe kill pelo fato de que o seu disco médio faz algo como 200 buscas aleatórias por segundo . Mas esse mesmo disco não tem problemas para ler ou gravar megabytes por segundo de dados sequencialmente. Qual é exatamente o que o mergesort faz.

Portanto, se os dados tiverem que ser classificados no disco, você realmente desejará usar alguma variação no mergesort. (Geralmente você sub-listas quicksort, em seguida, começar a mesclá-los juntos acima de algum limite de tamanho.)

Além disso, se você tiver que fazer qualquer coisa com conjuntos de dados desse tamanho, pense bastante sobre como evitar buscas em disco. Por exemplo, é por isso que é um conselho padrão descartar índices antes de executar grandes cargas de dados em bancos de dados e, em seguida, reconstruir o índice posteriormente. Manter o índice durante a carga significa constantemente procurar disco. Por outro lado, se você eliminar os índices, o banco de dados poderá reconstruir o índice, primeiro classificando as informações a serem tratadas (usando um conjunto de fusões, é claro!) E carregando-as em uma estrutura de dados BTREE para o índice. (BTREEs são naturalmente mantidos em ordem, então você pode carregar um de um conjunto de dados classificado com poucas buscas em disco.)

Houve várias ocasiões em que a compreensão de como evitar a procura de discos me permitiu fazer com que os trabalhos de processamento de dados demorassem horas em vez de dias ou semanas.

271
user11318

Na verdade, o QuickSort é O (n2). Seu caso médio tempo de execução é O (nlog (n)), mas seu pior caso é O (n2), que ocorre quando você o executa em uma lista que contém poucos itens exclusivos. A randomização leva O (n). Claro, isso não muda seu pior caso, apenas impede que um usuário mal-intencionado faça o seu tipo demorar muito tempo.

O QuickSort é mais popular porque:

  1. Está no local (MergeSort requer memória extra linear ao número de elementos a serem classificados).
  2. Tem uma pequena constante escondida.
87
Dark Shikari

"e, no entanto, a maioria das pessoas usa o Quicksort em vez do Mergesort. Por que isso acontece?"

Uma razão psicológica que não foi dada é simplesmente que Quicksort é mais inteligentemente chamado. ou seja, bom marketing.

Sim, o Quicksort com a divisão tripla é provavelmente um dos melhores algoritmos de classificação de propósitos gerais, mas não há como superar o fato de que a classificação "Rápida" soa muito mais poderosa do que a do tipo "Mesclar".

29
Ash

Como outros notaram, o pior caso do Quicksort é O (n ^ 2), enquanto o mergesort e o heapsort permanecem em O (nlogn). No caso médio, no entanto, todos os três são O (nlogn); então eles são para a grande maioria dos casos comparáveis.

O que torna o Quicksort melhor, em média, é que o laço interno implica em comparar vários valores com um único, enquanto no outro dois os dois termos são diferentes para cada comparação. Em outras palavras, o Quicksort faz metade das leituras dos outros dois algoritmos. Em CPUs modernas, o desempenho é fortemente dominado pelos tempos de acesso, então, no final, o Quicksort acaba sendo uma ótima primeira escolha.

15
Javier

Eu gostaria de acrescentar que dos três algoritmos mencionados até agora (mergesort, quicksort e heap sort) somente o mergesort é estável. Ou seja, o pedido não é alterado para aqueles valores que possuem a mesma chave. Em alguns casos isso é desejável.

Mas, verdade seja dita, em situações práticas a maioria das pessoas só precisa de um bom desempenho médio e o quicksort é ... rápido =)

Todos os algoritmos de ordenação têm seus altos e baixos. Veja artigo da Wikipedia para algoritmos de ordenação para uma boa visão geral.

8
Antti Rasinen

De a entrada da Wikipedia no Quicksort :

O Quicksort também concorre com o mergesort, outro algoritmo de classificação recursivo, mas com o benefício do pior tempo de execução (nlogn). O Mergesort é uma classificação estável, diferente do quicksort e do heapsort, e pode ser facilmente adaptado para operar em listas vinculadas e em listas muito grandes armazenadas em mídia de acesso lento, como armazenamento em disco ou armazenamento conectado à rede. Embora o quicksort possa ser escrito para operar em listas encadeadas, ele geralmente sofrerá de escolhas pivô ruins sem acesso aleatório. A principal desvantagem do mergesort é que, ao operar em arrays, ele requer auxilia (n) espaço auxiliar no melhor dos casos, enquanto a variante do quicksort com particionamento in-loco e recursão final usa apenas o espaço Θ (logn). (Observe que, ao operar em listas vinculadas, o mergesort requer apenas uma quantidade pequena e constante de armazenamento auxiliar.)

7
gnobal

Mu! O Quicksort não é melhor, é bem adequado para um tipo diferente de aplicação, do que o mergesort.

Vale a pena considerar o Mergesort se a velocidade for essencial, o pior desempenho do pior caso não puder ser tolerado e houver espaço extra disponível . 1

Você afirmou que eles "Ambos são O(nlogn) [...]". Isto está errado. "Quicksort usa sobre n ^ 2/2 comparações no pior dos casos." 1 .

No entanto, a propriedade mais importante, de acordo com a minha experiência, é a fácil implementação do acesso sequencial que você pode usar durante a classificação ao usar linguagens de programação com o paradigma imperativo.

1 Sedgewick, Algoritmos

7
Roman Glass

O Quicksort é o algoritmo de classificação mais rápido na prática, mas tem vários casos patológicos que podem fazer com que ele tenha um desempenho tão ruim quanto O (n2).

O Heapsort tem garantia de rodar em O (n * ln (n)) e requer apenas armazenamento adicional finito. Mas há muitas citações de testes do mundo real que mostram que o heapsort é significativamente mais lento que o quicksort em média.

6
Niyaz

A explicação da 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 quadrático. .

Quicksort

Mergesort

Eu acho que há também problemas com a quantidade de armazenamento necessária para o Mergesort (que é Ω (n)) que as implementações de quicksort não possuem. No pior dos casos, eles são a mesma quantidade de tempo algorítmico, mas o mergesort requer mais armazenamento.

5
Mat Mannion

Gostaria de acrescentar às grandes respostas existentes algumas contas sobre como o QuickSort se comporta quando divergindo dos melhores casos e qual a probabilidade disso, o que espero que ajude as pessoas a entender um pouco melhor porque o caso O (n ^ 2) não é real preocupação nas implementações mais sofisticadas do QuickSort.

Fora dos problemas de acesso aleatório, há dois fatores principais que podem afetar o desempenho do QuickSort e estão relacionados ao modo como o pivô se compara aos dados que estão sendo classificados.

1) Um pequeno número de chaves nos dados. Um conjunto de dados com o mesmo valor classificará em n ^ 2 vez em um QuickSort de 2 partições Vanilla, pois todos os valores, exceto o local dinâmico, serão colocados de um lado a cada vez. Implementações modernas abordam isso usando métodos como o uso de uma classificação de 3 partições. Esses métodos são executados em um conjunto de dados com o mesmo valor em O(n) tempo. Portanto, usar essa implementação significa que uma entrada com um pequeno número de chaves realmente melhora o tempo de desempenho e não é mais uma preocupação.

2) A seleção de pivôs extremamente ruim pode causar um desempenho pior. Em um caso ideal, o pivô sempre será tal que 50% dos dados são menores e 50% os dados são maiores, de modo que a entrada será dividida ao meio durante cada iteração. Isso nos dá n comparações e tempos de troca log-2 (n) recursões para O (n * logn) tempo.

Quanto a seleção de pivô não ideal afeta o tempo de execução?

Vamos considerar um caso em que o pivô é consistentemente escolhido de forma que 75% dos dados estejam em um lado do pivô. Ainda é O (n * logn) mas agora a base do log mudou para 1/0.75 ou 1.33. O relacionamento no desempenho ao mudar de base é sempre uma constante representada por log (2)/log (newBase). Nesse caso, essa constante é 2,4. Portanto, essa qualidade de escolha de pivô leva 2,4 vezes mais do que o ideal.

Quão rápido isso piora?

Não é muito rápido até que a escolha do pivô fique (consistentemente) muito ruim:

  • 50% de um lado: (caso ideal)
  • 75% de um lado: 2,4 vezes mais tempo
  • 90% de um lado: 6,6 vezes mais tempo
  • 95% de um lado: 13,5 vezes mais tempo
  • 99% de um lado: 69 vezes mais tempo

À medida que nos aproximamos 100% de um lado, a porção de log da execução se aproxima de n e toda a execução se aproxima assimptoticamente de O (n ^ 2).

Em uma implementação ingênua do QuickSort, casos como um array ordenado (para o primeiro elemento pivot) ou um array ordenado invertido (para o último elemento pivot) produzirão de forma confiável o pior tempo de execução O (n ^ 2). Além disso, implementações com uma seleção de pivot previsível podem ser submetidas a ataques DoS por dados projetados para produzir a pior execução. Implementações modernas evitam isso por uma variedade de métodos, como randomizar os dados antes de ordenar, escolher a mediana de 3 índices escolhidos aleatoriamente, etc. Com essa aleatorização no mix, temos dois casos:

  • Pequeno conjunto de dados. O pior caso é razoavelmente possível, mas O (n ^ 2) não é catastrófico porque n é pequeno o suficiente para que n ^ 2 também seja pequeno.
  • Grande conjunto de dados. O pior caso é possível em teoria, mas não na prática.

Qual a probabilidade de vermos um desempenho terrível?

As chances são muito pequenas . Vamos considerar uma espécie de 5.000 valores:

Nossa implementação hipotética escolherá um pivô usando uma média de 3 índices escolhidos aleatoriamente. Consideraremos pivots que estão na faixa de 25% -75% como "bons" e pivots que estão na faixa de 0% -25% ou 75% -100% como "ruins". Se você olhar para a distribuição de probabilidade usando a mediana de 3 índices aleatórios, cada recursão tem uma chance de 11/16 de acabar com um bom pivô. Vamos fazer duas suposições conservadoras (e falsas) para simplificar a matemática:

  1. Bons pivots estão sempre exatamente divididos em 25%/75% e operam em um case ideal de 2.4 *. Nunca conseguimos uma divisão ideal ou qualquer divisão melhor do que 25/75.

  2. Pivôs ruins são sempre os piores casos e essencialmente não contribuem com nada para a solução.

Nossa implementação do QuickSort irá parar em n = 10 e mudar para uma ordenação de inserção, então precisamos de 22 partições dinâmicas de 25%/75% para quebrar a entrada de 5.000 valores até esse ponto. (10 * 1.333333 ^ 22> 5000) Ou, precisamos de 4990 pivôs do pior caso. Tenha em mente que, se acumularmos 22 bons pivots em qualquer ponto , então o tipo será completado, então o pior caso ou qualquer coisa perto dele requer extremamente má sorte. Se nos levou 88 recursões para realmente alcançar os 22 bons pivôs requeridos para classificar em n = 10, isso seria 4 * 2.4 * caso ideal ou cerca de 10 vezes o tempo de execução do caso ideal. Qual a probabilidade de que não atinjam os 22 bons pivôs após 88 recursões?

Distribuições de probabilidade binomiais pode responder isso, e a resposta é de cerca de 10 ^ -18. (n é 88, k é 21, p é 0,6875) Seu usuário tem cerca de mil vezes mais chances de ser atingido por um raio no segundo que leva para clicar em [CLASSIFICAR] do que para ver que a tiragem de 5.000 itens qualquer caso pior do que 10 * ideal. Essa chance diminui conforme o conjunto de dados aumenta. Aqui estão alguns tamanhos de matrizes e suas chances correspondentes de correr mais de 10 * ideal:

  • Matriz de 640 itens: 10 ^ -13 (requer 15 bons pontos de pivot de 60 tentativas)
  • Matriz de 5.000 itens: 10 ^ -18 (requer 22 bons pivots de 88 tentativas)
  • Matriz de 40.000 itens: 10 ^ -23 (requer 29 bons pivots de 116)

Lembre-se de que isso é feito com duas suposições conservadoras que são piores que a realidade. Portanto, o desempenho real é melhor ainda, e o saldo da probabilidade restante é mais próximo do ideal do que não.

Finalmente, como outros já mencionaram, até esses casos absurdamente improváveis ​​podem ser eliminados mudando para um tipo de pilha se a pilha de recursão for muito profunda. Portanto, o TLDR é que, para boas implementações do QuickSort, o pior caso realmente não existe porque ele foi planejado e a execução é concluída no tempo O (n * logn).

4
Lance Wisely

O Quicksort NÃO é melhor que o mergesort. Com O (n ^ 2) (o pior caso que raramente acontece), o quicksort é potencialmente muito mais lento que o O(nlogn) da classificação de mesclagem. O Quicksort tem menos sobrecarga, portanto, com computadores pequenos n e lentos, é melhor. Mas os computadores são tão rápidos hoje que a sobrecarga adicional de um mergesort é insignificante, e o risco de um quicksort muito lento supera em muito a sobrecarga insignificante de um mergesort na maioria dos casos.

Além disso, um mergesort deixa itens com chaves idênticas em sua ordem original, um atributo útil.

4
xpda

Ao contrário do Merge Sort, o Quick Sort não usa um espaço auxiliar. Considerando que Merge Sort usa um espaço auxiliar O (n). Mas Merge Sort tem a pior complexidade de tempo de O(nlogn) enquanto a pior complexidade de Quick Sort é O (n ^ 2), o que acontece quando a matriz já está classificada.

3
Shantam Mittal

A resposta seria um pouco tilt para quicksort w.r.t para alterações trazidas com DualPivotQuickSort para valores primitivos. É usado em Java 7 para classificar 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 leitura impressionante em DualPivotQuickSort - http://permalink.gmane.org/gmane.comp.Java.openjdk.core-libs.devel/2628

3
SSR

Em merge-sort, o algoritmo geral é:

  1. Ordenar a sub-matriz esquerda
  2. Ordenar a sub-matriz correta
  3. Mesclar as duas sub-matrizes ordenadas

No nível superior, mesclar as duas sub-matrizes ordenadas envolve lidar com N elementos.

Um nível abaixo disso, cada iteração da etapa 3 envolve lidar com elementos N/2, mas você precisa repetir esse processo duas vezes. Então você ainda está lidando com elementos 2 * N/2 == N.

Um nível abaixo disso, você está mesclando 4 * N/4 == N elementos e assim por diante. Cada profundidade na pilha recursiva envolve mesclar o mesmo número de elementos, em todas as chamadas para essa profundidade.

Considere o algoritmo de ordenação rápida em vez disso:

  1. Escolha um ponto de pivô
  2. Coloque o ponto de giro no local correto na matriz, com todos os elementos menores à esquerda e os elementos maiores à direita
  3. Ordenar o subarray esquerdo
  4. Ordenar o subarray direito

No nível superior, você está lidando com uma matriz de tamanho N. Você escolhe um ponto de giro, coloca-o em sua posição correta e pode ignorá-lo completamente para o restante do algoritmo.

Um nível abaixo disso, você está lidando com dois sub-arrays que têm um tamanho combinado de N-1 (isto é, subtrair o ponto de giro anterior). Você escolhe um ponto de giro para cada subarray, que chega a até 2 pontos de pivô adicionais.

Um nível abaixo, você está lidando com 4 sub-arrays com tamanho combinado N-3, pelas mesmas razões acima.

Então N-7 ... Então N-15 ... Então N-32 ...

A profundidade da sua pilha recursiva permanece aproximadamente a mesma (logN). Com o merge-sort, você está sempre lidando com uma mesclagem N-element, em cada nível da pilha recursiva. Com a classificação rápida, o número de elementos com os quais você está lidando diminui à medida que você desce na pilha. Por exemplo, se você observar a profundidade no meio da pilha recursiva, o número de elementos com os quais você está lidando é N - 2 ^ ((logN)/2)) == N - sqrt (N).

Disclaimer: Em merge-sort, porque você divide o array em 2 partes exatamente iguais a cada vez, a profundidade recursiva é exatamente logN. Na classificação rápida, porque é improvável que seu ponto de articulação esteja exatamente no meio da matriz, a profundidade da sua pilha recursiva pode ser um pouco maior que logN. Eu não fiz as contas para ver o quão grande o papel deste fator e o fator descrito acima, realmente jogam na complexidade do algoritmo.

3
RvPr

O Quicksort tem uma complexidade de casos média melhor, mas em algumas aplicações é a escolha errada. O Quicksort é vulnerável a ataques de negação de serviço. Se um invasor puder escolher a entrada a ser classificada, ele poderá facilmente construir um conjunto que leve a complexidade de tempo do pior caso de o (n ^ 2).

A complexidade do caso médio do Mergesort e a complexidade do pior caso são as mesmas e, como tal, não sofrem o mesmo problema. Essa propriedade de merge-sort também a torna a melhor opção para sistemas em tempo real - precisamente porque não há casos patológicos que fazem com que ela funcione muito, muito mais devagar.

Sou mais fã do Mergesort do que do Quicksort, por estas razões.

2
Simon Johnson

Enquanto ambos estão na mesma classe de complexidade, isso não significa que ambos tenham o mesmo tempo de execução. O Quicksort é geralmente mais rápido que o mergesort, apenas porque é mais fácil codificar uma implementação rígida e as operações que ele executa podem ser mais rápidas. É porque esse quicksort é geralmente mais rápido do que as pessoas usam em vez de mergesort.

Contudo! Eu, pessoalmente, frequentemente utilizo o mergesort ou uma variante de quicksort que se degrada para o mergesort quando o quicksort não funciona bem. Lembrar. O Quicksort é apenas O (n log n) na média . O pior caso é O (n ^ 2)! O mergesort é sempre O (n log n). Nos casos em que o desempenho em tempo real ou a capacidade de resposta é uma obrigação e seus dados de entrada podem ser provenientes de uma fonte mal-intencionada, você não deve usar o quicksort simples.

2
DJ Capelis

A classificação rápida é o pior caso O (n ^ 2), no entanto, o caso médio consistentemente executa a ordenação por mesclagem. Cada algoritmo é O (nlogn), mas é preciso lembrar que quando falamos em Big O, deixamos de lado os fatores de menor complexidade. A classificação rápida apresenta melhorias significativas em relação à classificação por mesclagem quando se trata de fatores constantes.

Merge sort também requer O(2n) memory, enquanto quick sort pode ser feito no local (requerendo apenas O (n)). Esse é outro motivo pelo qual a classificação rápida geralmente é preferida em relação à classificação por mesclagem.

informação extra:

O pior caso de classificação rápida ocorre quando o pivô é mal escolhido. Considere o seguinte exemplo:

[5, 4, 3, 2, 1]

Se o pivô for escolhido como o menor ou maior número do grupo, a classificação rápida será executada em O (n ^ 2). A probabilidade de escolher o elemento que está no maior ou menor 25% da lista é 0,5. Isso dá ao algoritmo uma chance de 0,5 de ser um bom pivô. Se empregarmos um algoritmo de escolha de pivô típico (digamos, escolher um elemento aleatório), teremos 0,5 chance de escolher um bom pivô para cada escolha de um pivô. Para coleções de tamanho grande, a probabilidade de escolher sempre um pivô ruim é de 0,5 * n. Com base nessa probabilidade, a classificação rápida é eficiente para o caso médio (e típico).

2
Wade Anderson

Por que o Quicksort é bom?

  • O QuickSort leva N ^ 2 no pior caso e na média do NlogN. O pior caso ocorre quando os dados são classificados. Isso pode ser atenuado aleatoriamente antes da ordenação ser iniciada.
  • O QuickSort não leva memória extra que é obtida pela classificação de mesclagem.
  • Se o conjunto de dados for grande e houver itens idênticos, a complexidade do Quicksort será reduzida usando a partição de 3 vias. Mais o não de itens idênticos melhor o tipo. Se todos os itens forem idênticos, ele será classificado em tempo linear. [Esta é a implementação padrão na maioria das bibliotecas]

O Quicksort é sempre melhor que o Mergesort?

Na verdade não

  • O Mergesort é estável, mas o Quicksort não é. Então, se você precisa de estabilidade na saída, você usaria o Mergesort. A estabilidade é necessária em muitas aplicações práticas.
  • A memória é barata hoje em dia. Então, se a memória extra usada pelo Mergesort não é crítica para o seu aplicativo, não há mal nenhum em usar o Mergesort.

Nota: Em Java, a função Arrays.sort () usa o Quicksort para tipos de dados primitivos e o Mergesort para tipos de dados de objeto. Como os objetos consomem sobrecarga de memória, então, adicionar um pouco de sobrecarga para o Mergesort pode não ser um problema para o ponto de vista do desempenho.

Referência : Assista aos vídeos do QuickSort de Semana 3, Curso de Algoritmos de Princeton no Coursera

2
Sanjeev Kumar Dangi

Esta é uma pergunta bem antiga, mas desde que eu lidei com os dois recentemente, aqui está o meu 2c:

A ordenação por mesclagem precisa em média de comparações ~ N log N. Para arrays ordenados já (quase) ordenados, isto diminui para 1/2 N de log N, pois ao mesclar (quase) sempre selecionamos a parte "esquerda" 1/2 N de vezes e depois copiamos os elementos 1/2 N direito. Além disso, posso especular que a entrada já classificada faz o preditor da ramificação do processador brilhar, mas adivinhando quase todas as ramificações corretamente, evitando barracas de pipeline.

A classificação rápida, em média, requer comparações de ~ 1,38 N log N. Ele não se beneficia muito da matriz já ordenada em termos de comparações (no entanto, faz em termos de swaps e provavelmente em termos de predições de ramificação dentro da CPU).

Meus benchmarks em processadores razoavelmente modernos mostram o seguinte:

Quando a função de comparação é uma função de retorno de chamada (como na implementação qsort () libc), o quicksort é mais lento que o mergesort em 15% na entrada aleatória e em 30% para a matriz já classificada para inteiros de 64 bits.

Por outro lado, se a comparação não for um retorno de chamada, minha experiência é que o quicksort supera o fusível de até 25%.

No entanto, se a sua matriz (grande) tiver poucos valores exclusivos, a ordenação por mesclagem começa a ganhar mais do que o quicksort.

Então, talvez o resultado final seja: se a comparação é cara (por exemplo, função callback, comparação de strings, comparação de muitas partes de uma estrutura, na maior parte chegando a um segundo a terceiro) "se" fazer diferença) - as chances são de que você será melhor com merge sort. Para tarefas mais simples, o quicksort será mais rápido.

Dito tudo o que foi dito anteriormente é verdade: - O Quicksort pode ser N ^ 2, mas Sedgewick afirma que uma boa implementação aleatória tem mais chances de um computador executar uma espécie de ser atingido por um raio do que ir N ^ 2 - Mergesort requer espaço extra

2
virco

Quando experimentei os dois algoritmos de ordenação, contando o número de chamadas recursivas, o quicksort consistentemente tem menos chamadas recursivas do que o mergesort. É porque o quicksort tem pivots e os pivots não são incluídos nas próximas chamadas recursivas. Dessa forma, o quicksort pode alcançar o caso base recursivo mais rapidamente que o mergesort.

2
Aldian Fazrihady

Pequenas adições aos tipos rápidos e de mesclagem.

Também pode depender do tipo de itens de classificação. Se o acesso a itens, a troca e as comparações não forem operações simples, como a comparação de inteiros na memória plana, a ordenação por mesclagem pode ser um algoritmo preferível.

Por exemplo, classificamos itens usando o protocolo de rede no servidor remoto.

Além disso, em contêineres personalizados, como "lista vinculada", não há benefícios de classificação rápida.
1. Mesclar classificar na lista vinculada, não precisa de memória adicional. 2. O acesso aos elementos na classificação rápida não é sequencial (na memória)

1
minorlogic

Isso é difícil de dizer. O pior do MergeSort é n (log2n) -n + 1, que é preciso se n é igual a 2 ^ k (eu já provei isso) .E para qualquer n, é entre (n lg n - n + 1) e (ng n + n + O (lg n)) .Mas para quickSort, o melhor é nlog2n (também n é igual a 2 ^ k) .Se você divide o Mergesort por quickSort, é igual a um quando n é infinito. é como se o pior caso de MergeSort é melhor do que o melhor caso de QuickSort, por que usamos quicksort? Mas lembre-se, MergeSort não está no lugar, ele exige 2n memeroy space.And MergeSort também precisa fazer muitas cópias da matriz, que nós não inclua na análise do algoritmo. Em um Word, o MergeSort é realmente mais rápido do que o quicksort, mas na realidade você precisa considerar o espaço memeory, o custo da cópia do array, a fusão é mais lenta que o quick sort. experiência onde recebi 1000000 dígitos em Java pela classe Random, e levou 2610ms por mergesort, 1370ms por quicksort.

1
Peter

Sendo todas as coisas iguais, eu esperaria que a maioria das pessoas usasse o que estivesse mais convenientemente disponível, e isso tende a ser o qsort (3). Diferente do quicksort é conhecido por ser muito rápido em matrizes, assim como o mergesort é a escolha comum para listas.

O que eu estou querendo saber é porque é tão raro ver radix ou tipo de balde. Eles são O (n), pelo menos em listas vinculadas e tudo o que é necessário é algum método de converter a chave em um número ordinal. (strings e floats funcionam bem)

Estou pensando que a razão tem a ver com o modo como a ciência da computação é ensinada. Eu até tive que demonstrar ao meu professor na análise de algoritmos que era realmente possível classificar mais rápido que O (n log (n)). (Ele tinha a prova de que você não pode comparação classificar mais rápido que O (n log (n)), o que é verdade.)

Em outras notícias, os carros alegóricos podem ser classificados como números inteiros, mas você deve inverter os números negativos depois.

Edit: Na verdade, aqui está uma maneira ainda mais cruel para classificar floats-as-inteiros: http://www.stereopsis.com/radix.html . Observe que o truque de inversão de bits pode ser usado independentemente do algoritmo de classificação que você realmente usa ...

1
Anders Eurenius

Considere a complexidade do tempo e do espaço. Para Merge sort: Complexidade de tempo: O(nlogn), Complexidade de espaço: O (nlogn)

Para classificação rápida: complexidade do tempo: O (n ^ 2), complexidade do espaço: O (n)

Agora, ambos vencem em um scenerio cada. Mas, usando um pivô aleatório, você pode quase sempre reduzir a complexidade do Tempo de Classificação Rápida para O (nlogn).

Assim, a classificação rápida é preferida em muitos aplicativos, em vez da classificação de mesclagem.

0
pankaj

A classificação rápida é um algoritmo de classificação no local, por isso é mais adequado para matrizes. Merge sort, por outro lado, requer armazenamento extra de O (N) e é mais adequado para listas vinculadas.

Ao contrário das matrizes, na lista de gostos podemos inserir itens no meio com O(1) espaço e O(1) tempo, portanto a operação de mesclagem na classificação de mesclagem pode ser implementada sem qualquer espaço extra. No entanto, alocar e desalocar espaço extra para matrizes tem um efeito adverso no tempo de execução da classificação de mesclagem. A ordenação por mesclagem também favorece a lista vinculada à medida que os dados são acessados ​​sequencialmente, sem muito acesso à memória aleatória.

A ordenação rápida, por outro lado, requer muito acesso à memória aleatória e, com uma matriz, podemos acessar diretamente a memória sem precisar percorrer, conforme exigido pelas listas vinculadas. Também a classificação rápida quando usada para matrizes tem uma boa localidade de referência, pois as matrizes são armazenadas contiguamente na memória.

Embora a média de complexidade dos algoritmos de classificação seja O (NlogN), geralmente as pessoas para tarefas comuns usam uma matriz para armazenamento e, por esse motivo, a classificação rápida deve ser o algoritmo escolhido.

EDIT: Acabei de descobrir que merge classificar pior/melhor/avg caso é sempre nlogn, mas rápida classificar pode variar de n2 (pior caso quando os elementos já estão classificados) para nlogn (avg/melhor caso quando pivô sempre divide a matriz em dois metades).

0
Saad