Por que o quicksort é melhor que o mergesort?

StackOverflow https://stackoverflow.com/questions/70402

Pergunta

Essa pergunta me foi feita durante uma entrevista.Ambos são O(nlogn) e ainda assim a maioria das pessoas usa Quicksort em vez de Mergesort.Por que é que?

Foi útil?

Solução

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

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

Além disso, é muito fácil evitar o tempo de execução de pior caso do quicksort de O(n2) quase inteiramente usando uma escolha apropriada do pivô - como escolhê-lo aleatoriamente (esta é uma estratégia excelente).

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

Outras dicas

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

Na 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 for grande o suficiente para residir no disco, o quicksort será morto pelo fato de que seu disco médio faz algo em torno de 200 buscas aleatórias por segundo.Mas esse mesmo disco não tem problemas para ler ou gravar megabytes por segundo de dados sequencialmente.É exatamente isso que o mergesort faz.

Portanto, se os dados precisam ser classificados no disco, você realmente deseja usar alguma variação no mergesort.(Geralmente você classifica sublistas rapidamente e começa a mesclá-las acima de algum limite de tamanho.)

Além disso, se você tiver que fazer qualquer coisa com conjuntos de dados desse tamanho, pense bem em como evitar buscas no disco.Por exemplo, é por isso que é aconselhável descartar índices antes de realizar grandes carregamentos de dados em bancos de dados e, em seguida, reconstruir o índice posteriormente.Manter o índice durante o carregamento significa procurar constantemente o 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 mergesort, é claro!) e depois 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 no disco.)

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

Na verdade, QuickSort é O(n2).Isso é caso médio o tempo de execução é O (nlog (n)), mas é 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 o pior caso, apenas evita que um usuário mal-intencionado faça sua classificação demorar muito.

QuickSort é mais popular porque:

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

"e ainda assim a maioria das pessoas usa Quicksort em vez de Mergesort.Por que é que?"

Uma razão psicológica que não foi dada é simplesmente que Quicksort tem um nome mais inteligente.ou seja, um bom marketing.

Sim, o Quicksort com particionamento triplo é provavelmente um dos melhores algoritmos de classificação de uso geral, mas não há como superar o fato de que a classificação "Rápida" parece muito mais poderosa do que a classificação "Mesclar".

Como outros observaram, o pior caso de Quicksort é O(n^2), enquanto mergesort e heapsort permanecem em O(nlogn).No caso médio, entretanto, todos os três são O(nlogn);então eles são comparáveis ​​na grande maioria dos casos.

O que torna o Quicksort melhor em média é que o loop interno implica comparar vários valores com um único, enquanto nos outros dois ambos os termos são diferentes para cada comparação.Em outras palavras, o Quicksort faz metade das leituras que os 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.

Gostaria de acrescentar que dos três algoritmos mencionados até agora (mergesort, quicksort e heap sort), apenas o mergesort é estável.Ou seja, a ordem não muda para os valores que possuem a mesma chave.Em alguns casos isto é desejável.

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

Todos os algoritmos de classificação têm seus altos e baixos.Ver Artigo da Wikipedia sobre algoritmos de classificação para uma boa visão geral.

De a entrada da Wikipedia no Quicksort:

O Quicksort também compete com o Mergesort, outro algoritmo de classificação recursivo, mas com o benefício do pior caso θ (nLogn) tempo de execução.O Mergesort é um tipo estável, diferentemente do QuickSort e HeapSort, e pode ser facilmente adaptado para operar em listas vinculadas e listas muito grandes armazenadas em mídia lenta a acesso, como armazenamento de disco ou armazenamento de rede.Embora o QuickSort possa ser gravado para operar em listas vinculadas, muitas vezes sofre de más opções de pivô sem acesso aleatório.A principal desvantagem do mesclado é que, ao operar em matrizes, requer θ (n) espaço auxiliar na melhor das hipóteses, enquanto a variante do Quicksort com particionamento no local e recursão de cauda usa apenas θ (logn).(Observe que, ao operar em listas vinculadas, o Mergesort requer apenas uma quantidade pequena e constante de armazenamento auxiliar.)

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

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

Você afirmou que eles «são ambos O(nlogn) […]».Isto está errado.«Quicksort usa cerca de n ^ 2/2 comparações no pior caso.»1.

No entanto, a propriedade mais importante, de acordo com 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

Quicksort é o algoritmo de classificação mais rápido na prática, mas possui 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 execução 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.

A explicação da Wikipedia é:

Normalmente, o quicksort é significativamente mais rápido na prática do que outros algoritmos Θ(nlogn), porque seu loop interno pode ser implementado com eficiência na maioria das arquiteturas e, na maioria dos dados do mundo real, é possível fazer escolhas de design que minimizem a probabilidade de exigir tempo quadrático. .

Ordenação rápida

Mesclarsort

Acho que também há problemas com a quantidade de armazenamento necessária para Mergesort (que é Ω(n)) que as implementações de quicksort não possuem.Na pior das hipóteses, eles têm a mesma quantidade de tempo algorítmico, mas o mergesort requer mais armazenamento.

Quicksort NÃO é melhor que mergesort.Com O(n^2) (pior caso que raramente acontece), o quicksort é potencialmente muito mais lento que o O(nlogn) da classificação por mesclagem.O Quicksort tem menos sobrecarga, portanto, com computadores pequenos e lentos, é melhor.Mas os computadores são tão rápidos hoje em dia 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.

Gostaria de acrescentar às ótimas respostas existentes um pouco de matemática sobre o desempenho do QuickSort quando divergindo do melhor caso e qual a probabilidade disso, o que espero que ajude as pessoas a entender um pouco melhor por que o caso O (n ^ 2) não é real preocupação nas implementações mais sofisticadas do QuickSort.

Fora os problemas de acesso aleatório, há dois fatores principais que podem impactar o desempenho do QuickSort e ambos estão relacionados à forma 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 será classificado em n ^ 2 vezes em um QuickSort simples de 2 partições porque todos os valores, exceto o local do pivô, são colocados em um lado a cada vez.As implementações modernas abordam isso por meio de 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 tempo O(n).Portanto, usar tal 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) Uma seleção de pivô extremamente ruim pode causar o pior desempenho possível.Em um caso ideal, o pivô será sempre tal que 50% dos dados sejam menores e 50% dos dados sejam maiores, de modo que a entrada será quebrada ao meio durante cada iteração.Isso nos dá n comparações e trocas de tempo log-2(n) recursões por tempo O(n*logn).

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

Vamos considerar um caso em que o pivô é escolhido consistentemente 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.A relação de desempenho ao mudar de base é sempre uma constante representada por log(2)/log(newBase).Neste caso, essa constante é 2,4.Portanto, essa qualidade de escolha do pivô demora 2,4 vezes mais que o ideal.

Com que rapidez 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

À medida que nos aproximamos de 100% de um lado, a parte logarítmica da execução se aproxima de n e toda a execução se aproxima assintoticamente de O (n ^ 2).

Em uma implementação ingênua do QuickSort, casos como uma matriz classificada (para o pivô do primeiro elemento) ou uma matriz classificada inversamente (para o pivô do último elemento) produzirão de forma confiável um tempo de execução O (n ^ 2) de pior caso.Além disso, implementações com uma seleção de pivô previsível podem estar sujeitas a ataques DoS por dados projetados para produzir a execução do pior caso.As implementações modernas evitam isso por meio de uma variedade de métodos, como randomizar os dados antes da classificação, escolher a mediana de 3 índices escolhidos aleatoriamente, etc.Com essa randomização no mix, temos 2 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 na teoria, mas não na prática.

Qual é a probabilidade de vermos um desempenho terrível?

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

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

  1. Bons pivôs estão sempre exatamente em uma divisão de 25%/75% e operam no caso ideal de 2,4*.Nunca conseguimos uma divisão ideal ou qualquer divisão melhor que 25/75.

  2. Pivôs ruins são sempre o pior caso e essencialmente não contribuem em nada para a solução.

Nossa implementação QuickSort irá parar em n = 10 e mudar para uma classificação por inserção, portanto, precisamos de 22 partições dinâmicas de 25%/75% para dividir a entrada de 5.000 valores até esse ponto.(10*1,333333^22 > 5.000) Ou exigimos 4.990 pivôs de pior caso.Tenha em mente que se acumularmos 22 bons pivôs em qualquer ponto então a classificação será concluída, então o pior caso ou algo próximo disso requer extremamente má sorte.Se precisássemos de 88 recursões para realmente alcançar os 22 bons pivôs necessários para classificar até 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 alcançar os 22 bons pivôs necessários após 88 recursões?

Distribuições de probabilidade binomial posso responder isso, e a resposta é cerca de 10^-18.(n é 88, k é 21, p é 0,6875) Seu usuário tem cerca de mil vezes mais probabilidade de ser atingido por um raio no 1 segundo que leva para clicar em [SORT] do que ver aquela classificação de 5.000 itens executada pior de 10*caso ideal.Essa chance diminui à medida que o conjunto de dados aumenta.Aqui estão alguns tamanhos de array e suas chances correspondentes de durar mais que 10*ideal:

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

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

Finalmente, como outros mencionaram, mesmo esses casos absurdamente improváveis ​​podem ser eliminados mudando para uma classificação por heap 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 foi projetado e a execução é concluída em tempo O (n * logn).

A resposta seria ligeiramente inclinada para quicksort em relação às mudanças trazidas com DualPivotQuickSort para valores primitivos.É usado em JAVA7 classificar 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 implementação JAVA7 aqui - http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7-b147/java/util/Arrays.java

Outras leituras incríveis no DualPivotQuickSort - http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628

No merge-sort, o algoritmo geral é:

  1. Classifique a submatriz esquerda
  2. Classifique a submatriz correta
  3. Mesclar as 2 submatrizes classificadas

No nível superior, mesclar as 2 submatrizes classificadas envolve lidar com N elementos.

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

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

Considere o algoritmo de classificação rápida:

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

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

Um nível abaixo disso, você está lidando com 2 submatrizes que possuem um tamanho combinado de N-1 (ou seja, subtrai o ponto de pivô anterior).Você escolhe um ponto de pivô para cada submatriz, o que resulta em 2 pontos de pivô adicionais.

Um nível abaixo disso, você está lidando com 4 submatrizes com tamanho combinado N-3, pelos mesmos motivos 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ê sempre lida com uma mesclagem de N elementos, em cada nível da pilha recursiva.Porém, 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).

Isenção de responsabilidade:Na classificação por mesclagem, como você divide a matriz em 2 partes exatamente iguais a cada vez, a profundidade recursiva é exatamente logN.Na classificação rápida, como é improvável que seu ponto pivô esteja exatamente no meio da matriz, a profundidade de sua pilha recursiva pode ser um pouco maior que logN.Não fiz as contas para ver o tamanho do papel que esse fator e o fator descrito acima realmente desempenham na complexidade do algoritmo.

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

Embora ambos estejam 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 restrita e as operações que ele executa podem ser mais rápidas.É porque o quicksort geralmente é mais rápido que as pessoas o usam em vez do mergesort.

No entanto!Pessoalmente, muitas vezes usarei o mergesort ou uma variante do quicksort que se degrada para o mergesort quando o quicksort funciona mal.Lembrar.Quicksort é apenas O (n log n) ativado média.O pior caso é O (n ^ 2)!Mergesort é sempre O(n log n).Nos casos em que o desempenho ou a capacidade de resposta em tempo real são essenciais e seus dados de entrada podem vir de uma fonte maliciosa, você não deve usar o quicksort simples.

Quicksort tem uma complexidade média de caso melhor, mas em algumas aplicações é a escolha errada.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 considere a complexidade de tempo do pior caso de o(n^2).

A complexidade média e a complexidade do pior caso do Mergesort são iguais e, como tal, não sofrem o mesmo problema.Essa propriedade do merge-sort também o torna a escolha superior para sistemas em tempo real - precisamente porque não há casos patológicos que façam com que ele funcione muito, muito mais lentamente.

Sou mais fã do Mergesort do que do Quicksort, por esses motivos.

Por que o Quicksort é bom?

  • QuickSort leva N ^ 2 no pior caso e NlogN no caso médio.O pior caso ocorre quando os dados são classificados.Isso pode ser mitigado por embaralhamento aleatório antes do início da classificação.
  • QuickSort não ocupa memória extra usada pela classificação por 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.Quanto mais o número de itens idênticos, melhor a classificação.Se todos os itens forem idênticos, ele classifica em tempo linear.[Esta é a implementação padrão na maioria das bibliotecas]

O Quicksort é sempre melhor que o Mergesort?

Na verdade.

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

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

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

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

A classificação por mesclagem também requer memória O(2n), enquanto a classificação rápida pode ser feita no local (exigindo apenas O(n)).Esse é outro motivo pelo qual a classificação rápida é geralmente preferida à 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á nos 25% maiores ou menores da lista é de 0,5.Isso dá ao algoritmo 0,5 de chance de ser um bom pivô.Se empregarmos um algoritmo típico de escolha de pivô (digamos, escolher um elemento aleatório), teremos 0,5 chance de escolher um bom pivô para cada escolha de pivô.Para coleções de tamanho grande a probabilidade de sempre escolher um pivô ruim é de 0,5 * n.Com base nesta probabilidade, a classificação rápida é eficiente para o caso médio (e típico).

Esta é uma pergunta bastante antiga, mas como lidei com ambas recentemente, aqui estão meus 2c:

A classificação por mesclagem precisa, em média, de ~ N log N comparações.Para matrizes classificadas já (quase) classificadas, isso cai para 1/2 N log N, pois durante a fusão, nós (quase) sempre selecionamos a parte "esquerda" 1/2 N de vezes e, em seguida, apenas copiamos 1/2 N elementos à direita.Além disso, posso especular que a entrada já classificada faz o preditor de ramificação do processador brilhar, mas adivinha quase todas as ramificações corretamente, evitando assim travamentos do pipeline.

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

Meus benchmarks em processadores bastante 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 30% para array já classificado para números 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 mergesort em até 25%.

No entanto, se o seu array (grande) tiver poucos valores exclusivos, a classificação por mesclagem começa a ganhar mais do que o quicksort em qualquer caso.

Então, talvez o resultado final seja:se a comparação for cara (por ex.função de retorno de chamada, comparando strings, comparando muitas partes de uma estrutura, principalmente chegando a um segundo-terço-quarto "se" para fazer a diferença) - as chances são de que você se sairá melhor com a classificação por mesclagem.Para tarefas mais simples, o quicksort será mais rápido.

Dito isto, tudo o que foi dito anteriormente é verdade:- O Quicksort pode ser n^2, mas Sedgewick afirma que uma boa implementação randomizada tem mais chances de um tipo de computador executar a classificação a ser atingido por um raio do que ir n^2 - o mesclar requer espaço extra

Quando experimentei os dois algoritmos de classificação, contando o número de chamadas recursivas, o Quicksort tem consistentemente chamadas recursivas do que o mesclado.Isso ocorre porque o quicksort tem pivôs e os pivôs 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.

Se todas as coisas forem iguais, espero que a maioria das pessoas use o que estiver mais convenientemente disponível, e isso tende a ser qsort(3).Fora isso, o quicksort é conhecido por ser muito rápido em arrays, assim como o mergesort é a escolha comum para listas.

O que me pergunto é por que é tão raro ver raiz ou classificação de balde.Eles são O(n), pelo menos em listas vinculadas e basta algum método para converter a chave em um número ordinal.(cordas e carros alegóricos funcionam perfeitamente.)

Estou pensando que o motivo tem a ver com a forma como a ciência da computação é ensinada.Eu até tive que demonstrar ao meu professor de 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 números flutuantes podem ser classificados como números inteiros, mas você terá que inverter os números negativos depois.

Editar:Na verdade, aqui está uma maneira ainda mais cruel de classificar números flutuantes como números 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...

Isso é difícil de dizer. O pior do MergeSort é n (log2n) -n + 1, que é preciso se n for igual a 2 ^ k (já provei isso). E para qualquer n, está entre (n lg n - n + 1) e (n lg n + n + O (lg n)). Mas para quickSort, seu melhor é nlog2n (também n é igual a 2 ^ k). Se você dividir Mergesort por quickSort, será igual a um quando n for infinito. é como se o pior caso do MergeSort fosse melhor do que o melhor caso do QuickSort, por que usamos o quicksort? Mas lembre-se, o MergeSort não está em vigor, ele requer 2n espaço memeroy. E o MergeSort também precisa fazer muitas cópias do array, o que nós não inclua na análise do algoritmo. Em uma palavra, MergeSort é realmente mais rápido do que quicksort no theroy, mas na realidade você precisa considerar o espaço de memória, o custo da cópia do array, a fusão é mais lenta do que a classificação rápida. experimento onde recebi 1.000.000 dígitos em java pela classe Random, e demorou 2.610 ms por mergesort, 1370 ms por quicksort.

Pequenas adições às classificações rápidas e mescladas.

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

Por exemplo, classificamos itens usando protocolo de rede em um servidor remoto.

Além disso, em contêineres personalizados como "lista vinculada", não há benefício na classificação rápida.
1.Mesclar classificação 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)

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

Ao contrário dos arrays, na lista curtida podemos inserir itens no meio com espaço O(1) e tempo O(1), portanto, a operação de mesclagem na classificação por mesclagem pode ser implementada sem nenhum 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 por mesclagem.A classificação por mesclagem também favorece a lista vinculada, pois os dados são acessados ​​sequencialmente, sem muito acesso aleatório à memória.

A classificação rápida, por outro lado, requer muito acesso aleatório à memória e, com um array, podemos acessar diretamente a memória sem qualquer deslocamento, conforme exigido pelas listas vinculadas.A classificação rápida também, quando usada para matrizes, tem uma boa localidade de referência, pois as matrizes são armazenadas contíguamente na memória.

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

EDITAR:Acabei de descobrir que a classificação de pior/melhor/médio caso de mesclagem é sempre nlogn, mas a classificação rápida pode variar de n2 (pior caso quando os elementos já estão classificados) a nlogn (média/melhor caso quando o pivô sempre divide a matriz em duas metades) .

Considere a complexidade do tempo e do espaço.Para classificação de mesclagem:Complexidade de tempo:O (nLogn), complexidade espacial:O(nlogn)

Para classificação rápida:Complexidade de tempo:O (n^2), complexidade espacial:Sobre)

Agora, os dois vencem em um cenário cada.Mas, usando um pivô aleatório, você quase sempre pode reduzir a complexidade de tempo da classificação rápida para O (nlogn).

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

Na terra C/C ++, quando não estiver usando contêineres STL, eu tendem a usar o Quicksort, porque ele está incorporado ao tempo de execução, enquanto o Mergesort não é.

Portanto, acredito que, em muitos casos, é simplesmente o caminho de menor resistência.

Além disso, o desempenho pode ser muito maior com a classificação rápida, para casos em que todo o conjunto de dados não cabe no conjunto de trabalho.

Uma das razões é mais filosófica.Quicksort é a filosofia Top->Down.Com n elementos para classificar, existem n!possibilidades.Com 2 partições de m e n-m que são mutuamente exclusivas, o número de possibilidades diminui em várias ordens de grandeza.m!* (n-m)!é menor em vários pedidos do que n!sozinho.imagine 5!contra 3!*2!.5!tem 10 vezes mais possibilidades do que 2 partições de 2 e 3 cada.e extrapolar para 1 milhão fatorial vs 900K!*100K!vs.Portanto, em vez de se preocupar em estabelecer qualquer ordem dentro de um intervalo ou partição, basta estabelecer a ordem em um nível mais amplo nas partições e reduzir as possibilidades dentro de uma partição.Qualquer ordem estabelecida anteriormente dentro de um intervalo será perturbada posteriormente se as próprias partições não forem mutuamente exclusivas.

Qualquer abordagem de ordem ascendente, como classificação por mesclagem ou classificação por heap, é como uma abordagem de trabalhadores ou funcionários, onde se começa a comparar em um nível microscópico desde o início.Mas esta ordem está fadada a ser perdida assim que um elemento entre eles for encontrado mais tarde.Essas abordagens são muito estáveis ​​e extremamente previsíveis, mas exigem uma certa quantidade de trabalho extra.

Quick Sort é como uma abordagem gerencial em que inicialmente não se preocupa com nenhum pedido, apenas em atender a um critério amplo, sem consideração pelo pedido.Em seguida, as partições são reduzidas até obter um conjunto classificado.O verdadeiro desafio no Quicksort é encontrar uma partição ou critério no escuro quando você não sabe nada sobre os elementos a serem classificados.É por isso que precisamos despender algum esforço para encontrar um valor mediano ou escolher 1 aleatoriamente ou alguma abordagem "gerencial" arbitrária.Encontrar uma mediana perfeita pode exigir um esforço significativo e leva novamente a uma abordagem estúpida de baixo para cima.Então, o Quicksort diz apenas para escolher um pivô aleatório e esperar que esteja em algum lugar no meio ou fazer algum trabalho para encontrar a mediana de 3, 5 ou algo mais para encontrar uma mediana melhor, mas não planeje ser perfeito e não desperdice a qualquer momento no pedido inicial.Isso parece funcionar bem se você tiver sorte ou às vezes degrada para n ^ 2 quando você não obtém uma mediana, mas apenas arrisca.De qualquer forma, os dados são aleatórios.certo.Então, eu concordo mais com a abordagem lógica de cima -> para baixo do quicksort e acontece que a chance necessária sobre a seleção de pivôs e comparações que ele salva anteriormente parece funcionar melhor mais vezes do que qualquer abordagem meticulosa e completa e estável de baixo -> para cima como classificação de mesclagem.Mas

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top