Quicksort: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
Etiquetas: Inserção do elemento "nowiki", possivelmente errônea Editor Visual |
|||
Linha 158:
## Parte III: Com índices de G + 1 até o último elemento a direita, contendo os elementos superiores P2.
## Parte IV: contendo os elementos a ser examinados com índices de K até G
## O próximo elemento na posição K pertencente a parte IV é comparado com os pivôs P1 e P2, e alocado na parte correspondente, I, II ou III.
#### Os ponteiros L, K e G são alterados nas direções correspondentes.
#### Os passos 4 e 5 são repetidos enquanto G se aproxima de K.
#### O pivô P1 é trocado com o último elemento da parte I, o pivô P2 é trocado com o primeiro elemento da parte III.
#### As etapas 1 e 7 são repetidas de forma recursiva para cada parte I, II e III.
#### Também foi demonstrado por Yaroslavskiy<ref>YAROSLAVSKIY, V. Dual-pivot quicksort. Research Disclosure, 2009.[http://www.kriche.com.ar/root/programming/spaceTimeComplexity/DualPivotQuicksort.pdf <nowiki>[1]</nowiki>]</ref> que para ordenação de dados primitivos é mais eficiente a utilização do quicksort de 3 partições, sendo o número médio de comparações do Dual-Pivot Quicksort é <math>\mathcal ({2})n\ln(n)</math>, e o número médio de trocas é <math>\mathcal ({0,8})n\ln(n)</math>, enquanto a versão clássica do algoritmo Quicksort possui <math>\mathcal ({2})n\ln(n)</math> e <math>\mathcal (1)n\ln(n)</math>, respectivamente.
##
#
| |||