Se você está vendo esta mensagem, significa que estamos tendo problemas para carregar recursos externos em nosso website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

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 n elementos leva Θ(n) de tempo. Cada elemento 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 n elementos, o tempo da partição é Θ(n): tempo-linear de particionamento.
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?

Você entende inglês? Clique aqui para ver mais debates na versão em inglês do site da Khan Academy.