Por que quicksort é melhor que mergesort?

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

Quicksort tem O ( n ² ) tempo de execução do pior caso e O ( n log n ) tempo de execução médio. No entanto, é superior mesclar a classificação em muitos cenários, porque muitos fatores influenciam o tempo de execução de um algoritmo e, ao reuni-los todos juntos, o quicksort vence.

Em particular, o tempo de execução frequentemente mencionado dos algoritmos de classificação refere-se ao número de comparações ou ao número de trocas necessárias para realizar a classificaçã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, lemos muitos elementos que provavelmente estão no cache?) - também desempenham um papel importante no hardware atual. O Quicksort, em particular, requer pouco espaço adicional e exibe boa localidade do cache, e isso torna mais rápido que a classificação de mesclagem em muitos casos.

Além disso, é muito fácil evitar o pior tempo de execução do quicksort de O ( n ² ) quase inteiramente usando uma escolha apropriada do pivô - como escolher aleatoriamente (essa é uma excelente estratégia).

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

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

Na RAM, essa suposição geralmente não é ruim (nem sempre é verdade por causa dos caches, mas não é ruim). No entanto, se sua estrutura de dados é grande o suficiente para viver em disco, em seguida, quicksort se matou pelo fato de que o disco médio faz algo como 200 aleatória busca 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 deseja usar alguma variação no mergesort. (Geralmente você sublinha rapidamente, em seguida, começa a mesclá-las acima de algum limite de tamanho.)

Além disso, se você precisar fazer algo com conjuntos de dados desse tamanho, pense bem em como evitar buscas em disco. Por exemplo, é por isso que é aconselhável que você solte índices antes de fazer grandes carregamentos de dados nos bancos de dados e depois reconstrua o índice posteriormente. Manter o índice durante o carregamento significa procurar constantemente no disco. Por outro lado, se você soltar os índices, o banco de dados poderá reconstruir o índice, classificando primeiro as informações a serem tratadas (usando uma combinação de cursos, é claro!) E, em seguida, carregando-as em uma estrutura de dados BTREE para o índice. (Os BTREEs são mantidos naturalmente em ordem, para que você possa 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 buscas em disco me permitiu que os trabalhos de processamento de dados levassem horas, em vez de dias ou semanas.

Na verdade, o QuickSort é O (n ² ). Seu tempo médio de execução de caso é O (nlog (n)), mas o pior caso é O (n ² ), que ocorre quando você o executa em uma lista que contém poucos itens exclusivos. A randomização leva O (n). Obviamente, isso não muda o pior dos casos, apenas impede que um usuário mal-intencionado faça com que sua classificação demore 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 oculta.

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

Uma razão psicológica que não foi apresentada é simplesmente que o Quicksort é chamado de maneira mais inteligente. ou seja, 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 que a classificação "Mesclar".

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

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 os dois termos são diferentes para cada comparação. Em outras palavras, o Quicksort faz metade do número de leituras que os outros dois algoritmos. Nas CPUs modernas, o desempenho é fortemente dominado pelos tempos de acesso, portanto, no final, o Quicksort acaba sendo uma ótima primeira escolha.

Eu gostaria de acrescentar que, dos três algoritmos mencionados até agora (fusão, classificação rápida e classificação de heap), apenas a fusão é estável. Ou seja, a ordem não muda para os valores que têm a mesma chave. Em alguns casos, isso é 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 é ... quick =)

Todos os algoritmos de classificação têm seus altos e baixos. Consulte o artigo da Wikipedia para classificar algoritmos para obter uma boa visão geral.

Na entrada da Wikipedia no Quicksort :

O Quicksort também concorre com o mergesort, outro algoritmo de classificação recursiva, mas com o benefício do pior caso running (nlogn) do tempo de execução. O mergesort é uma classificação estável, ao contrário 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 anexado à rede. Embora o quicksort possa ser gravado para operar em listas vinculadas, geralmente sofre de más escolhas de pivô sem acesso aleatório. A principal desvantagem do mergesort é que, ao operar em matrizes, ele requer Θ (n) espaço auxiliar no melhor dos casos, enquanto a variante do quicksort com particionamento no local e recursão de cauda usa apenas espaço Θ (logn). (Observe que, ao operar em listas vinculadas, o mergesort requer apenas uma quantidade pequena e constante de armazenamento auxiliar.)

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

Vale a pena considerar o Mergesort se a velocidade é essencial, o pior desempenho do pior caso não pode ser tolerado e o espaço extra está disponível. 1 1

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

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

1 Sedgewick, Algoritmos

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

É garantido que o Heapsort seja executado em O (n * ln (n)) e requer apenas armazenamento adicional finito. Mas existem 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 n (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 minimizam a probabilidade de exigir tempo quadrático. .

Ordenação rápida

Mergesort

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

Gostaria de acrescentar às ótimas respostas existentes algumas contas sobre o desempenho do QuickSort ao divergir do melhor caso e qual a probabilidade disso, o que espero 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 dos problemas de acesso aleatório, existem dois fatores principais que podem afetar o desempenho do QuickSort e ambos estão relacionados à forma como o pivot 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 em um QuickSort de 2 partições de baunilha, porque todos os valores, exceto o local da tabela dinâmica, são colocados em um lado de cada vez. As implementações modernas tratam disso por 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ô extremamente ruim pode causar o pior desempenho possível. Em um caso ideal, o pivô sempre será tal que 50% dos dados são menores e 50% dos 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 pelo 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 modo 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 alterar a base é sempre uma constante representada por log (2) / log (newBase). Nesse caso, essa constante é 2,4. Portanto, essa qualidade de escolha do pivô leva 2,4 vezes mais tempo 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
• 90% de um lado: 6,6 vezes mais
• 95% de um lado: 13,5 vezes mais
• 99% de um lado: 69 vezes mais

À medida que nos aproximamos de 100% de um lado, a parte do log 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 1º elemento dinâmico) ou uma matriz classificada inversa (para o último elemento dinâmico) produzirão de maneira confiável o pior tempo de execução de O (n ^ 2). Além disso, implementações com uma seleção de pivô previsível podem ser sujeitas a ataques de DoS por dados projetados para produzir a pior execução possível. As implementações modernas evitam isso por uma variedade de métodos, como aleatorizar os dados antes da classificação, escolher a mediana de 3 índices escolhidos aleatoriamente, etc. Com essa aleatorização no mix, temos 2 casos:

• Conjunto de dados pequeno. 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.
• Conjunto de dados grande. 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 muito pequenas . 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 no intervalo de 25% a 75% como "bons" e os pivôs que estão no intervalo 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 uma chance de 11/16 de terminar com um bom pivô. Vamos fazer 2 suposições conservadoras (e falsas) para simplificar a matemática:

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

2. Os pivôs ruins são sempre os piores casos e, essencialmente, não contribuem para a solução.

Nossa implementação do QuickSort irá parar em n = 10 e mudar para uma classificação de inserção, portanto, precisamos de 22 partições dinâmicas de 25% / 75% para quebrar a entrada de 5.000 valores até o momento. (10 * 1,333333 ^ 22> 5000) Ou exigimos 4990 pivôs do pior caso. Tenha em mente que se acumulam 22 bons pivôs em qualquer ponto , em seguida, o tipo completará, então pior caso ou qualquer coisa perto que exige extremamente má sorte. Se precisássemos de 88 recursões para atingir os 22 bons pivôs necessários para classificar até n = 10, seria um caso ideal de 4 * 2,4 * ou cerca de 10 vezes o tempo de execução do caso ideal. Qual a probabilidade de não conseguirmos os 22 bons pivôs necessários após 88 recursões?

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

• Matriz de 640 itens: 10 ^ -13 (requer 15 pontos de articulação bons em 60 tentativas)
• Matriz de 5.000 itens: 10 ^ -18 (requer 22 rotações dinâmicas em 88 tentativas)
• Matriz de 40.000 itens: 10 ^ -23 (requer 29 boas pivôs de 116)

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

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

Por que o Quicksort é bom?

• O QuickSort aceita N ^ 2 no pior caso e NlogN no caso médio. O pior caso ocorre quando os dados são classificados. Isso pode ser atenuado por reprodução aleatória antes de a classificação ser iniciada.
• O QuickSort não ocupa memória extra, obtida por 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úmero de itens idênticos melhor o tipo. Se todos os itens forem idênticos, serão classificados 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. 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 haverá danos ao usar o Mergesort.

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

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

O Quicksort NÃO é melhor que o mergesort. Com O (n ^ 2) (pior caso que raramente acontece), a classificação rápida é potencialmente muito mais lenta que o O (nlogn) da classificação de mesclagem. O Quicksort tem menos sobrecarga; portanto, com computadores pequenos e lentos, é melhor. Hoje, porém, os computadores são tão rápidos que a sobrecarga adicional de uma associação de fusão é desprezível, e o risco de uma associação rápida muito lenta supera em muito a sobrecarga insignificante de uma associação de fusão na maioria dos casos.

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

A resposta levaria um pouco a direção do quicksort wrt para as alterações trazidas com o DualPivotQuickSort para valores primitivos. É usado no 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 implementação JAVA7 aqui - http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7-b147/java/util/Arrays.java

Outras leituras impressionantes sobre o DualPivotQuickSort - http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628

Na classificação por mesclagem, o algoritmo geral é:

1. Classifique o subconjunto esquerdo
2. Classifique o subconjunto certo
3. Mesclar as duas sub-matrizes classificadas

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ê deve 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. Toda profundidade na pilha recursiva envolve a mesclagem 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 articulação no local correto da matriz, com todos os elementos menores à esquerda e elementos maiores à direita
3. Classificar a sub-matriz esquerda
4. Classificar a sub-matriz direita

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

Um nível abaixo disso, você está lidando com 2 sub-matrizes que têm um tamanho combinado de N-1 (ou seja, subtrai o ponto de pivô anterior). Você escolhe um ponto de articulação para cada sub-matriz, que chega a 2 pontos de articulação adicionais.

Um nível abaixo disso, você está lidando com 4 sub-matrizes 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 a classificação de mesclagem, você está sempre lidando com uma mesclagem de elemento N, em cada nível da pilha recursiva. Com a classificação rápida, porém, o número de elementos com os quais você está lidando diminui à medida que você desce a 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, porque 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 o seu ponto de articulação esteja exatamente no meio da matriz, a profundidade da sua pilha recursiva pode ser um pouco maior que o logN. Eu não fiz as contas para ver o tamanho do papel que esse fator e o fator descrito acima desempenham na complexidade do algoritmo.

Ao contrário de 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 a pior complexidade de O (nlogn), enquanto a pior complexidade de Quick Sort é O (n ^ 2), o que acontece quando a matriz já está classificada.

O Quicksort tem uma complexidade média melhor, mas em alguns aplicativos é a escolha errada. O Quicksort é vulnerável a ataques de negação de serviço. Se um invasor pode escolher a entrada a ser classificada, ele pode facilmente construir um conjunto que considere a pior complexidade de tempo (o) (n ^ 2).

A complexidade média dos casos do Mergesort e a complexidade dos piores casos são os mesmos e, como tal, não sofrem o mesmo problema. Essa propriedade de classificação por mesclagem também a torna a escolha superior 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 esses motivos.

Isso é difícil de dizer. O pior do MergeSort é n (log2n) -n + 1, que é preciso se n for igual a 2 ^ k (eu 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, o 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 do QuickSort, por que usamos o quicksort? Mas lembre-se, o MergeSort não está no lugar, requer 2n de espaço de memória.E o MergeSort também precisa fazer muitas cópias de matriz, que nós Não inclua na análise do algoritmo.Em uma palavra, o MergeSort é realmente mais rápido que o quicksort, mas na realidade você precisa considerar o espaço da memória, o custo da cópia do array, a fusão é mais lenta que a classificação rápida. experimento em que recebi 1000000 dígitos em java pela classe Random,e foram necessários 2610ms por fusão, 1370ms por quicksort.

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

A ordenação por mesclagem também requer memória O (2n), enquanto a ordenação rápida pode ser feita no local (requerendo 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 o maior número no 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 é 0,5. Isso dá ao algoritmo uma chance de 0,5 de ser um bom pivô. Se empregarmos um algoritmo típico de escolha de pivô (por exemplo, escolher um elemento aleatório), temos 0,5 chance de escolher um bom pivô para cada escolha de um pivô. Para coleções de tamanho grande, a probabilidade de sempre escolher 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).

Esta é uma pergunta bastante antiga, mas desde que eu lidei com as duas recentemente, aqui estão os meus 2c:

As necessidades de classificação de mesclagem, em média, ~ N log N comparações. Para matrizes classificadas já (quase) classificadas, isso reduz a 1/2 N log N, pois durante a mesclagem sempre (quase) selecionamos a parte "esquerda" 1/2 N vezes e depois copiamos os elementos 1/2 N à direita. Além disso, posso especular que a entrada já classificada faz com que o preditor de ramificação do processador brilhe, mas adivinhando quase todas as ramificações corretamente, impedindo assim a interrupção do pipeline.

A ordenação rápida, em média, requer comparações de ~ 1,38 N log N. Ele não se beneficia muito da matriz já classificada em termos de comparações (no entanto, em termos de swaps e provavelmente em termos de previsões de ramificações 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 da libs do qsort ()), o quicksort é mais lento do que o mergesort em 15% na entrada aleatória e 30% na matriz já classificada 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 resultado da fusão em até 25%.

No entanto, se sua matriz (grande) tiver muito poucos valores exclusivos, a classificação de mesclagem começará a ganhar mais que a quicksort em qualquer caso.

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

Dito isso, 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 classificação ser atingido por um raio do que ir N ^ 2 - O Mergesort requer espaço extra

Quando experimentei os dois algoritmos de classificação, contando o número de chamadas recursivas, o quicksort consistentemente tem menos chamadas recursivas do que o mergesort. Isso ocorre porque o quicksort possui 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 do que o mergesort.

Essa é uma pergunta comum nas entrevistas que, apesar do melhor desempenho de pior caso da classificação por mesclagem, o quicksort é considerado melhor que a classificação por mesclagem, especialmente para uma entrada grande. Existem algumas razões pelas quais o quicksort é melhor:

1- Espaço Auxiliar: classificação rápida é um algoritmo de classificação no local. A classificação no local significa que não é necessário espaço de armazenamento adicional para realizar a classificação. A classificação de mesclagem, por outro lado, requer uma matriz temporária para mesclar as matrizes classificadas e, portanto, não está no local.

2- Pior caso: O pior caso do quicksort O(n^2)pode ser evitado usando o quicksort aleatório. Pode ser facilmente evitado com alta probabilidade, escolhendo o pivô certo. Obter um comportamento de caso médio, escolhendo o elemento de pivô correto, melhora o desempenho e se torna tão eficiente quanto a classificação de mesclagem.

3- Localidade de referência: O Quicksort, em particular, exibe boa localização do cache e isso torna mais rápido que a classificação por mesclagem em muitos casos, como no ambiente de memória virtual.

4- Recursão da cauda: o QuickSort é recursivo da cauda, ​​enquanto a classificação Merge não. Uma função recursiva da cauda é uma função em que a chamada recursiva é a última coisa executada pela função. As funções recursivas da cauda são consideradas melhores que as funções recursivas não-cauda, ​​pois a recursão da cauda pode ser otimizada pelo compilador.

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 do que o mergesort, apenas porque é mais fácil codificar uma implementação rígida e as operações que ele realiza podem ser mais rápidas. É porque esse quicksort é geralmente mais rápido que as pessoas o usam, em vez de mesclar.

Contudo! Pessoalmente, frequentemente utilizarei o mergesort ou uma variante de quicksort que degrada para mergesort quando o quicksort se sai mal. Lembrar. Quicksort é apenas O (n log n) em média . O pior caso é O (n ^ 2)! O mergesort é sempre O (n log n). Nos casos em que o desempenho ou a capacidade de resposta em tempo real são obrigatórios e os dados de entrada podem ser provenientes de uma fonte maliciosa, você não deve usar o quicksort simples.

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

O que estou querendo saber é por que é tão raro ver tipos de radix ou bucket. Eles são O (n), pelo menos em listas vinculadas e basta um método de converter a chave em um número ordinal. (cordas e flutuadores funcionam muito bem.)

Eu estou pensando que o motivo tem a ver com o ensino da ciência da computação. Eu até tive que demonstrar ao meu professor de análise de algoritmo que era realmente possível classificar mais rapidamente que O (n log (n)). (Ele tinha a prova de que você não pode comparar a classificação mais rapidamente 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ê precisa mudar os números negativos depois.

Edit: Na verdade, aqui está uma maneira ainda mais cruel de classificar carros alegóricos 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 ...

Pequenas adições às classificações rápidas vs de mesclagem.

Também pode depender do tipo de itens de classificação. Se o acesso a itens, trocas e comparações não for operações simples, como comparar números inteiros na memória plana, a classificaçã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ício da classificação rápida.
1. Mesclar a classificação na lista vinculada, não precisa de memória adicional. 2. O acesso a elementos em ordenação rápida não é seqüencial (na memória)

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

Diferentemente das matrizes, na lista de gostos, podemos inserir itens no meio com espaço O (1) e tempo O (1), portanto, a operação de mesclagem na classificação de mesclagem pode ser implementada sem nenhum espaço extra. No entanto, alocar e desalocar espaço extra para matrizes têm 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 ordenação rápida, por outro lado, exige muito acesso aleatório à memó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 complexidade média de ambos os 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 de escolha.

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

Considere a complexidade do tempo e do espaço. Para classificação de mesclagem: complexidade do tempo: O (nlogn), complexidade do 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 cenário cada. Porém, usando um pivô aleatório, quase sempre é possível 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 de mesclagem.

No terreno do c / c ++, quando não estou usando contêineres stl, costumo usar o quicksort, porque ele é incorporado no tempo de execução, enquanto o mergesort não.

Então, 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, nos casos em que o conjunto de dados inteiro não se encaixa no conjunto de trabalho.

Um dos motivos é mais filosófico. Quicksort é a filosofia Top-> Down. Com n elementos para classificar, existem n! possibilidades. Com 2 partições de m & nm que são mutuamente exclusivas, o número de possibilidades diminui em várias ordens de magnitude. m! * (nm)! é menor por várias ordens que n! sozinho. imagine 5! vs 3! * 2! 5! tem 10 vezes mais possibilidades do que 2 partições de 2 e 3 cada. e extrapolar para 1 milhão de 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 pedido estabelecido anteriormente dentro de um intervalo será interrompido posteriormente se as próprias partições não forem mutuamente exclusivas.

Qualquer abordagem de ordem de baixo para cima, como classificação de mesclagem ou classificação de pilha, é como uma abordagem de trabalhadores ou funcionários, em que se começa a comparar cedo e em nível microscópico. Mas essa ordem provavelmente será perdida assim que um elemento entre eles for encontrado mais tarde. Essas abordagens são muito estáveis ​​e extremamente previsíveis, mas executam uma certa quantidade de trabalho extra.

A Classificação Rápida é semelhante à abordagem gerencial, na qual não se preocupa inicialmente com nenhum pedido, apenas com o cumprimento de um critério amplo sem consideração à ordem. Em seguida, as partições são reduzidas até você obter um conjunto classificado. O verdadeiro desafio do 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 dedicar algum esforço para encontrar um valor mediano ou escolher 1 aleatoriamente ou em uma abordagem "gerencial" arbitrária. Encontrar uma mediana perfeita pode exigir um esforço significativo e leva a uma abordagem estúpida de baixo para cima novamente. Portanto, o Quicksort diz apenas que escolha um pivô aleatório e espere que esteja em algum lugar no meio ou faça algum trabalho para encontrar a mediana de 3, 5 ou algo mais para encontrar uma mediana melhor, mas não planeje ser perfeito. Não perca tempo solicitando inicialmente. Isso parece funcionar bem se você tiver sorte ou, às vezes, degradar para n ^ 2 quando não obtiver uma mediana, mas apenas arriscar. De qualquer maneira, os dados são aleatórios. direita. Então, eu concordo mais com a abordagem lógica de cima para baixo do quicksort e acontece que a chance de seleção de pivôs e comparações que ele salva anteriormente parece funcionar melhor mais vezes do que qualquer abordagem meticulosa e completa de baixo para cima, como mesclar classificação. Mas as comparações que ele salva anteriormente parecem funcionar melhor mais vezes do que qualquer abordagem meticulosa e minuciosa e estável de baixo para cima, como a classificação por mesclagem. Mas as comparações que ele salva anteriormente parecem funcionar melhor mais vezes do que qualquer abordagem meticulosa e minuciosa e estável de baixo para cima, como a classificação por mesclagem. Mas