Algoritmo de ordenação Quick Sort (Partição Hoare)

Trecho de código do algoritmo Quick Sort usando a partição Hoare

Durante a implementação de um sistema ou de uma nova funcionalidade, a equipe de desenvolvimento responsável deve tomar inúmeras decisões que afetam de alguma forma o produto destinado para o cliente final. Uma dessas escolhas, sobretudo quando há a necessidade de classificar os dados consumidos pelo usuário da aplicação, é decidir o algoritmo de ordenação mais eficiente possível no contexto do projeto.

O algoritmo Quick Sort se notabiliza por ser um dos melhores no segmento da ordenação, tendo em vista o equilíbrio que ele possui entre a sua complexidade de tempo e o uso do espaço auxiliar de memória, característica que está detalhada nas próximas seções do artigo. Além disso, o Quick Sort tem uma flexibilidade singular, dado o vasto rol existente de estratégias de particionamento do array de input.

Aliás, no que tange as variações do algoritmo, o Quick Sort costuma se beneficiar de três técnicas populares de partição de elementos. A que apresenta menor nível de performance é a Naive Partition, também conhecida como Partição Simples. Já a Lomuto Partition e a Hoare's Partition são os métodos com maior desempenho.

Entendendo o algoritmo

Por padrão, o Quick Sort se comporta de modo recursivo, compartilhando uma semelhança com o algoritmo Merge Sort. Entretanto, as instruções de recursão no Quick Sort são as últimas presentes na função, à medida que no Merge Sort, os comandos de recursividade figuram no início do procedimento. De bate pronto, essa diferença não aparenta ter relevância, mas impacta diretamente na eficiência do algoritmo.

Contudo, antes de esmiuçar as particularidades da recursão do Quick Sort, darei um passo atrás para destacar a importância da rotina de particionamento. Nesse caso, a análise será especificamente direcionada à Partição Hoare. Sem a sua compreensão, não há outro jeito de dominar o algoritmo.

A Partição Hoare

As funções de particionamento dependem de um pivô. Esse item dita a maneira que os demais números serão ordenados dentro da estrutura. Na Partição Hoare, o primeiro elemento do vetor assume o posto de pivô.

Uma vez que o pivô foi determinado, o método de particionamento inicia a sua lógica de ordenação do array. A Partição Hoare realoca os números menores do que o pivô à esquerda, e os números maiores do que o pivô à direita. Combinada à recursividade do Quick Sort, a função de partição ordena o vetor em fases, até que reste apenas um item para ser classificado.

O reposicionamento dos elementos na Partição Hoare ocorre através de duas variáveis de controle, apelidadas de i e j. A variável i aponta para o começo do array, mantendo os números inferiores em relação ao pivô. Por sua vez, a variável j aponta para o fim do array, mantendo os números superiores em relação ao pivô.

Enquanto os números localizados no índice i forem menores do que o pivô, esta variável de controle é incrementada continuamente. Por outro lado, enquanto os números que residem no índice j forem maiores do que o pivô, esta variável de controle é decrementada indefinidamente.

Se as variáveis i e j não se cruzarem (i < j) durante as suas respectivas inspeções, os elementos presentes nos índices i e j trocam de posição. No entanto, essa alternância acontece somente sob duas condições: um número maior do que o pivô for encontrado na varredura feita pelo índice i, e um número menor do que o pivô for identificado na varredura exercida pelo índice j.

Todavia, na hipótese de as variáveis i e j se cruzarem (i >= j), a rotina de particionamento encerra o seu processo, retornando o valor do índice j. O racional por trás disso está no fato que todos os números até a posição j são menores do que o pivô, e os números a partir de j + 1 são maiores ou iguais ao pivô.

Um exemplo prático

Execução do algoritmo Quick Sort com base na Partição Hoare

A imagem acima mostra justamente como o Quick Sort ordena um vetor alicerçado na Partição Hoare. O entendimento completo da execução do algoritmo reside em uma avaliação minuciosa dos seis passos realçados na figura.

1. A função Quick Sort recebe o vetor { 5, 2, 10, 8, 11, 4 } a ser ordenado. Os parâmetros de controle inicio e fim apontam para o índice zero e n - 1 (onde n representa a quantidade total de elementos) da estrutura, respectivamente.
• Sendo assim, o método de particionamento percorre todos os itens do array, selecionando o número cinco como pivô.
• No ciclo inicial da Partição Hoare, o número cinco troca de posição com o número quatro, e com isto o vetor sofre a sua primeira modificação: { 4, 2, 10, 8, 11, 5 }.
• Após a troca de elementos, as variáveis de controle i e j da Partição Hoare se cruzam (i >= j). Enquanto i aponta para o índice dois, j aponta para o índice um (índice de partição). Consequentemente, a rotina de particionamento termina a sua execução, retornando o valor do índice j.
2. A função Quick Sort faz uma chamada recursiva, desta vez reduzindo o intervalo do vetor de input. O parâmetro de controle inicio permanece apontando para o índice zero, mas o parâmetro de controle fim aponta para o índice um.
• Então, o procedimento da Partição Hoare itera somente pelo subarray { 4, 2 }, escolhendo o número quatro como pivô.
• O número quatro troca de posição com o número dois, resultando em uma alteração no subarray: { 2, 4 }.
• Depois da troca de elementos, as variáveis de controle i e j da Partição Hoare se cruzam (i >= j). Enquanto i aponta para o índice um, j aponta para o índice zero (índice de partição). O método de particionamento finaliza a sua execução, retornando o valor do índice j.
3. A função Quick Sort realiza mais uma chamada recursiva, diminuindo o intervalo do vetor de input. O parâmetro de controle inicio continua apontando para o índice zero. Contudo, o parâmetro de controle fim também aponta para o índice zero. Isso significa que o array está irredutível. 
4. Temos o término do empilhamento de chamadas recursivas do lado esquerdo da árvore de execução do Quick Sort. A função retoma o seu processamento a partir do ponto no qual a primeira recursão foi acionada. Dessa forma, a variável de particao aponta para o índice um, e a variável de controle fim para o índice n - 1 (onde n representa a quantidade total de elementos).
• Dado que a segunda chamada recursiva de Quick Sort estabelece o início do subarray em particao + 1, a função da Partição Hoare percorre apenas os elementos { 10, 8, 11, 5 }, elegendo o número dez como pivô. Os itens { 2, 4 } são descartados nesta etapa, pois foram devidamente ordenados no passo anterior.
• O número dez troca de posição com o número cinco, ocasionando uma modificação no subarray: { 5, 8, 11, 10 }.
• Na sequência da troca de elementos, as variáveis de controle i e j da Partição Hoare se cruzam (i >= j). O ponteiro i está no índice quatro, e o ponteiro j está no índice três (índice de partição). Portanto, a rotina de particionamento encerra a sua execução, retornando o valor do índice j.
5. A função Quick Sort faz outra chamada recursiva, limitando o intervalo do vetor de input. O parâmetro de controle inicio aponta para o índice dois, e o parâmetro de controle fim aponta para o índice três. Em virtude de o subarray { 5, 8 } estar ordenado, a Partição Hoare conclui a sua execução de modo instantâneo, e novamente o vetor atinge um estado irredutível.
6. A função Quick Sort volta para o processamento do Passo 4. Com isso, a variável de particao aponta para o índice três, e a variável de controle fim para o índice n - 1 (onde n representa a quantidade total de elementos).
• Em razão de a segunda chamada recursiva de Quick Sort demarcar o início do subarray como particao + 1, o método da Partição Hoare itera apenas nos itens { 11, 10 }, escolhendo o número onze como pivô. Os itens { 2, 4, 5, 8 } são descartados nesta etapa, porque foram ordenados nos passos anteriores.
• O número onze troca de posição com o número dez, gerando uma alteração no subarray: { 10, 11 }.
• As variáveis de controle i e j da Partição Hoare se cruzam (i >= j). O ponteiro i aponta para o índice cinco, e o ponteiro j para o índice quatro (índice de partição). À vista disso, a função de particionamento acaba a sua execução, retornando o valor do índice j.
• O array de input finalmente tem os seus números ordenados: { 2, 4, 5, 8, 10, 11 }. Todas as chamadas recursivas que foram empilhadas são integralizadas, e a função Quick Sort para a sua execução.

Analisando a implementação do algoritmo

O Quick Sort faz parte do grupo de algoritmos de ordenação com complexidade média de tempo em O(n*log(n)). Na sua pior conjuntura, quando há uma má seleção do elemento pivô, a complexidade de tempo atinge o patamar de O(n²).

Conforme ressaltado de antemão, a recursividade no Quick Sort detém uma peculiaridade notável: as suas duas chamadas recursivas estão localizadas no final da função. Em situações como essa, as instruções em questão são intituladas de chamada de cauda.

Os procedimentos com recursão de cauda costumam ostentar uma performance superior. Isso porque os compiladores modernos otimizam funções de tal natureza, removendo as chamadas recursivas. 

Na prática, os compiladores identificam a última recursão, adicionam um rótulo no início (start), atualizam os parâmetros de input e reexecutam a rotina com o artifício do goto.

Comparando o desempenho do algoritmo com o Merge Sort

Sob a óptica da análise assintótica, os algoritmos Quick Sort e Merge Sort se equivalem no que diz respeito à complexidade de tempo. Ambos dispõe de uma complexidade de O(n*log(n)), propriedade que lhes garante um status privilegiado no ranking dos algoritmos de ordenação mais eficientes.

Entretanto, a partir de um conjunto de testes real, no qual um vetor com dez, cem, mil, dez mil e cem mil elementos é classificado em ordem crescente, constatamos que o Merge Sort alcança uma média de tempo superior do que o Quick Sort.

Método	Input	Média de tempo	Espaço alocado
MétodoQuickSort	InputInt32[10]	Média de tempo58.80 ns	Espaço alocado-
MétodoMergeSort	InputInt32[10]	Média de tempo204.51 ns	Espaço alocado624 B
MétodoQuickSort	InputInt32[100]	Média de tempo57.212 ns	Espaço alocado-
MétodoMergeSort	InputInt32[100]	Média de tempo37.910 ns	Espaço alocado8000 B
MétodoQuickSort	InputInt32[1000]	Média de tempo173,618.67 ns	Espaço alocado-
MétodoMergeSort	InputInt32[1000]	Média de tempo36,003.92 ns	Espaço alocado92304 B
MétodoQuickSort	InputInt32[10000]	Média de tempo16,464,618.96 ns	Espaço alocado19 B
MétodoMergeSort	InputInt32[10000]	Média de tempo436,978.94 ns	Espaço alocado1072016 B
MétodoQuickSort	InputInt32[100000]	Média de tempo1,696,434,546.32 ns	Espaço alocado38 B
MétodoMergeSort	InputInt32[100000]	Média de tempo5,513,068.47 ns	Espaço alocado12031270 B

Mas, graças à recursão de cauda e a estratégia de particionamento, o Quick Sort aufere uma vantagem competitiva em detrimento do Merge Sort. O consumo do espaço auxiliar de memória do Quick Sort em praticamente todos os testes realizados não se altera, ou seja, está em um nível constante. 

Já o Merge Sort aloca mais memória de acordo com o crescimento da quantidade de elementos, pois a sua lógica de ordenação requer a criação de vetores auxiliares de tamanho n (onde n representa a número total de itens).

O código-fonte dos algoritmos e os detalhes extras acerca de seus respectivos desempenhos estão disponíveis no meu repositório do Github.