Estou aprendendo sobre o quicksort e quero ilustrar matrizes diferentes nas quais o quicksort teria dificuldade. O quicksort que eu tenho em mente não possui um embaralhamento aleatório inicial, faz 2 partições e não calcula a mediana.
Pensei em três exemplos até agora:
[1,2,3,4,5,6,7,8,9,10] - when the array is sorted
[10,9,8,7,6,5,4,3,2,1] - when the array is reversed
[1,1,1,1,1,1,1,1,1,1] - when the array is the same values
[1,1,1,2,2,2,3,3,3,3] - when there are few and unique keys
Por exemplo, não tenho muita certeza sobre este:
[1,3,5,7,9,10,8,6,4,2]
Então, o que cria uma matriz com a qual o quicksort tem dificuldade em comparação com uma onde é (quase) ideal?
algorithms
sorting
mrQWERTY
fonte
fonte
[2,1,2,1,2,1,2,1]e que é a totalidade responda). O objetivo da pergunta seria, idealmente, aquele em que outras pessoas possam vir e descobrir mais sobre o porquê (que tem uma resposta) e não exemplos (dos quais existem inúmeras).Respostas:
Todo algoritmo de classificação tem o pior caso e, em muitos casos, o pior é muito ruim, portanto vale a pena testá-lo. O problema é que não existe um pior caso apenas porque você conhece o algoritmo básico.
Os piores casos comuns incluem: já classificados; ordenado ao contrário; quase classificado, um elemento fora de ordem; todos os valores são iguais; todos iguais, exceto o primeiro (ou o último) é mais alto (ou mais baixo). Certa vez, tivemos um tipo em que o pior caso era um padrão de dente de serra específico, que era muito difícil de prever, mas bastante comum na prática.
O pior caso para o quicksort é aquele que sempre escolhe o pior pivô possível, para que uma das partições tenha apenas um elemento. Se o pivô for o primeiro elemento (má escolha), os dados já classificados ou inversos serão o pior caso. Para uma mediana de três dados dinâmicos iguais ou apenas o primeiro ou o último diferentes, o truque.
Para quicksort, a complexidade média é nlogn e o pior caso é n ^ 2. O motivo pelo qual vale a pena desencadear o comportamento do pior caso é porque esse também é o caso que produz a maior profundidade de recursão. Para uma implementação ingênua, a profundidade da recursão pode ser n, o que pode disparar o estouro da pilha. Testar outras situações extremas (incluindo o melhor caso) pode valer a pena por razões semelhantes.
fonte
O(NlogN)desempenho médio ou melhor), os piores e médios casos têm a mesma complexidade. Isso sugere que geralmente NÃO vale a pena testar nos piores casos. (Tendo em conta que o teste é provavelmenteO(N)... ou pior.)Um algoritmo escapa da maioria dos casos ruins usando um pivô aleatório, excluindo elementos contínuos iguais a um pivô do particionamento e da pesquisa assimétrica. Ele pesquisa para frente um elemento maior ou igual a um pivô e pesquisa para trás um elemento menor que um pivô.
Agradeço a MichaelT, a pesquisa assimétrica é planejada para resolver [2,1,2,1,2,1,2,1].
O seguinte resultado é gerado pela minha função qsort_random (). N = 100.000
A maioria dos casos é mais rápida que um padrão aleatório. O padrão de vale é um caso ruim para a maioria das seleções dinâmicas.
qsort_log2 () foge de caso incorreto selecionando um pivô nos elementos log2 (N).
O qsort (3) usa a biblioteca GNU, que é uma espécie de mesclagem de classificação de índice.
qsort_trad () seleciona um pivô no primeiro, no meio e no último elemento.
qsort_random () e qsort_log2 () não usam troca.
Os programas e scripts de origem C são publicados no github .
fonte