Usar a média como pivô aceleraria o quicksort?

7

De alguma forma, pensei sobre o quicksort ontem à noite e estava lendo sobre isso na Wikipedia. A parte interessante para mim foi: 'Se pudéssemos escolher consistentemente um pivô dos 50% médios, teríamos que dividir a lista no máximolog4/3n. A escolha do pivô parece ser um possível problema do quicksort que pode levar aO(n2) comportamento.

Minha idéia era: se em cada etapa se usasse a média da partição como pivô , isso poderia aumentar significativamente a velocidade. Especialmente depois de algumas etapas, quando os outliers estão em sua própria divisão da lista, a média e a mediana devem estar muito próximas umas das outras (mais uma vez, olhando para listas grandes). O tempo adicional durante cada etapa para calcular a média deve sern. Portanto:

Tempo estimado do Quicksort: nAlog4/3n

Tempo estimado de Quicksort_mean: 2nAlog5/3n

(5/3 é provavelmente uma estimativa conservadora da minha parte, também poderia estar mais próxima de 2, pois os subconjuntos devem ficar rapidamente sem discrepâncias). Portanto, a partir de 10.000 entradas, o Quicksort_mean seria (em média) mais rápido que o Quicksort. Além disso, nunca arriscaria serO(n2), pois ele não aceita o elemento mínimo ou máximo da pilha.

Minha principal pergunta é: eu perdi alguma coisa? Eu tenho que admitir, eu nunca implementei o quicksort, então posso perder outras partes da coisa toda (armazenamento, etc.)

Johannes Becker
fonte
11
Você realmente resolveu a recorrência atualizada para obter esse "tempo de execução" ou apenas adicionou outro n? (Este último seria errado.)
Raphael
(isenção de responsabilidade: faz muito tempo desde que eu olhei seriamente para essas coisas, e meu conhecimento pode estar desatualizado) A classificação rápida é apenas um fator dois mais rápido do que seus principais concorrentes, que têm um bom comportamento de pior caso. tornar a classificação rápida significativamente mais lenta, na melhor das hipóteses, elimina o motivo para usá-lo em vez de outros algoritmos.
Eu simplesmente adicionei outro n. Eu sei que está 'errado', mas o cálculo da média deve ser super rápido (n adições, o que pode ser feito durante a classificação e o número de divisões de partições). Meu conhecimento sobre os concorrentes não é muito bom (como eu disse, era apenas um pensamento completamente aleatória sendo meio adormecido ...)
Johannes Becker

Respostas:

10

O uso da média para sua partição não impede que o Ω(n2)pior comportamento. Ocorre quando a lista de entrada está aumentando exponencialmente. Considere a entrada:

1,n2,n3,,nn

A média deste conjunto é (assintoticamente) nn1para que você obtenha a pior partição possível. Isso é meio trapaceiro, considerando que o armazenamento da lista levaΩ(n2)espaço se os números forem representados como números inteiros. Mas se você estiver classificando números de ponto flutuante, esse cenário é visível.

No entanto, é possível calcular a mediana de um conjunto (ou qualquer outra estatística de ordem para esse assunto) emO(n) tempo, por isso, se você realmente se importa com as garantias de tempo de execução para uma classificação rápida, use isso em vez da média.

No entanto, em todos os cenários práticos, o custo adicional de calcular a média / mediana é tão grande que escolher um pivô aleatório quase sempre é mais rápido.

Tom van der Zanden
fonte
Essa é uma lista média: D (eu acho que você alcançaria o infinito rapidamente, para não ter um número muito alto n). Meu argumento era que O (n) não é automaticamente O (n). Em comparação, o cálculo da mediana é A * n com A maior que 1. Em comparação, o cálculo da média deve estar próximo de 1 * n. Então, acho que isso poderia aumentar a média do tempo de execução (não estava interessado nas garantias de tempo de execução). Eu tenho que admitir, a coisa toda foi apenas uma linha de pensamento que não me deixou em paz esta noite. Então eu decidi colocá-lo aqui em achados alguém caso interessante ...
Johannes Becker
11
O último parágrafo é muito importante: sim, você pode otimizar a profundidade da recursão escolhendo pivôs melhores, mas tem um custo. É necessária uma análise rigorosa para determinar se vale a pena. Veja, por exemplo, a tese de Sedgewick; a resposta costuma ser "não" (intuição: você sempre paga pela escolha de pivôs melhores, mas apenas algumas vezes pela escolha de forma mais ingênua).
Raphael
Muitos critérios de classificação não têm uma "média", por exemplo, classificando uma lista de pessoas pelo sobrenome.
precisa saber é o seguinte