Conteúdo principal
Particionamento em tempo linear
O verdadeiro trabalho da ordenação rápida acontece durante a etapa de divisão, que partições sub arranjo
array[p..r]
em volta de m pivô extraído de um sub arranjo. Embora nós podemos escolher qualquer elemento no sub arranjo como pivô, é fácil de implementar a partição se nós escolhermos o elemento mais a direita do sub arranjo, A[r]
, como o pivô.Tendo escolhido um pivô, podemos particionar o sub arranjo passando por ele, da esquerda para a direita comparando cada elemento com o pivô. Nós matemos dois índices
q
e j
no subarranjo que divide em quatro grupos. Nós usamos o nome da variável q
porque esse índice irá apontar para o nosso pivô. Nós usamos j
porque é um nome comum para uma variável de contagem, e a variável será descartada quando terminarmos.- Os elementos no
array[p..q-1]
são do "group L," que consiste de elementos conhecidos como sendo menores ou iguais ao pivô. - Os elementos no
array[q..j-1]
são do "group G," que consiste de elementos conhecidos como sendo mairoes ou iguais ao pivô. - Os elementos no
array[j..r-1]
são do "group U," que consiste de elementos relacionados com o pivô é desconhecida, porque eles ainda não foram comparados. - Finalmente,
array[r]
é "group P," o p ivô.
Inicialmente, ambos
q
e j
igual a p
. A cada passo, nós comparamos A[j]
, o elemento mais à esqueda no grupo U, com o pivô. Se A[j]
é maior que o pivô, então nós incrementamos j
, para que a linha que divide os grupos G e U deslize uma posição para a direita:Se em vez disso
A[j]
for menor ou igual ao pivô, então nós trocamos A[j]
por A[q]
(o elemento mais a esquerda no grupo G), incrementamos j
, e incrementamos q
, deslocando assim a linha que divide os grupos L e G e a linha que divide os grupos G e U em uma posição para a direita:Quando chegamos ao pivô, o grupo U está vazio. Trocamos o pivô com o elemento mais à esquerda no grupo G: troque
A[r]
por A[q]
. Essa troca coloca o pivô entre os grupos L e G, e faz a coisa certa mesmo se o grupo L ou o grupo G estiver vazio. A função
partição
que implementa essa ideia também retorna o índice q
onde acabou colocando o pivô, para que a função quicksort
, que realiza a chamada, saiba onde estão as partições. Estas são as etapas do particionamento do subarray [12, 7, 14, 9, 10, 11] em
array[4..9]
:Particionando um sub arranjo com elementos leva de tempo. Cada elemento elementos, o tempo da partição é : tempo-linear de particionamento.
A[j]
é comparado uma vez com o pivô. A[j]
poderia ou pode não ser trocado por A[q]
, q
pode ou poderia não ser incrementado, e j
é sempre incrementado. O número total de linhas executadas por elemento no sub arranjo é uma constante. Desde que o sub arranjo tem Este conteúdo é uma colaboração entre os professores de ciência da computação da Universidade de Dartmouth, Thomas Cormen e Devin Balkcom, juntamente com a equipe do currículo de computação da Khan Academy. O conteúdo é licenciado CC-BY-NC-SA.
Quer participar da conversa?
- A tradução deste artigo está muito ruim.(1 voto)