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.

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 $\mathrm{\Theta }(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 é $\mathrm{\Theta }(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.