DC-UFRPE/Bacharelado em Ciência da Computação/Algoritmos e Estruturas de Dados/Quicksort
Quick Sort é um algoritmo eficiente de ordenação por divisão e conquista. Apesar de ser da mesma classe de complexidade do Merge Sort e do Heap Sort, o Quick Sort é na prática o mais veloz deles, pois suas constantes são menores. Contudo, é importante destacar de antemão que, em seu pior caso, o Quick Sort é , enquanto que o Merge Sort e o Heap Sort garantem
para todos os casos. A boa notícia é que há estratégias simples com as quais podemos minimizar as chances de ocorrência do pior caso.
O funcionamento do Quick Sort baseia-se em uma rotina fundamental cujo nome é particionamento. Particionar significa escolher um número qualquer presente no array, chamado de pivot, e colocá-lo em uma posição tal que todos os elementos à esquerda são menores ou iguais e todos os elementos à direita são maiores.
Particionamento editar
Vamos particionar o array [3, 8, 7, 10, 0, 23, 2, 1, 77, 7]. Saiba, não vou entrar em detalhes sobre como é feito o particionamento agora. Isso será feito mais adiante neste material. Neste momento minha preocupação é que você saiba o que é particionar, não como. Então, vamos ver o estado do array antes e depois de particionar. Como disse, precisamos escolher um pivot. Por ora, vamos sempre escolher o primeiro elemento do array. Ou seja, nosso pivot é o valor 3.
Antes do particionamento: [3, 8, 7, 10, 0, 23, 2, 1, 77, 7]
Depois do particionamento: [1, 0, 2, 3, 8, 23, 7, 10, 77, 7]
Note que todos os elementos à esquerda do pivot são menores ou iguais ao pivot e todos os elementos à direita do pivot são maiores. Isso não significa que os elementos à esquerda e à direita devem necessariamente estar ordenados. Apenas significa que o pivot está em sua posição e o problema de ordenar agora resume-se a resolver a esquerda dele e a direita dele, concorda?
Já que entendemos o que é particionamento, vamos agora ver como este algoritmo funciona. Há duas estratégias populares de particionamento: Lomuto e Hoare. Neste material nós vamos abordar a estratégia de Lomuto, que é mais simples.
A ideia do particionamento de Lomuto é identificar os elementos menores ou iguais ao pivot e colocá-los imediatamente à frente dele. Depois, no final, coloca-se o pivot à frente deles todos. Vamos ver um exemplo concreto para ver como funciona essa ideia.
Para o array [3, 8, 7, 10, 0, 23, 2, 1, 77, 7], temos que o pivot é igual a 3. Vamos iterar no array identificando os elementos menores ou iguais a ele. O primeiro identificado é o valor 0.
values = [3, 8, 7, 10, 0, 23, 2, 1, 77, 7]
Nosso trabalho agora é colocar o valor 0 à frente do pivot. Então, trocamos esse valor com o valor 8 (imediatamente à frente de 3). Note, no estado parcial, que 0 ficou à frente de 3 e 8 assumiu o índice de 0.
values = [3, 0, 7, 10, 8, 23, 2, 1, 77, 7]
Temos que trazer 2 para a frente de 3. Vamos fazer isso trocando este valor com o valor 7. Veja, no estado parcial, que agora os valores 0 e 2 estão à frente de 3.Acabou? Não. O próximo elemento menor ou igual ao pivot (3) é 1.
values = [3, 0, 2, 10, 8, 23, 7, 1, 77, 7]
Temos que trazer 1 para a frente de 3. Vamos fazer isso trocando este valor com o valor 10. Veja, no estado parcial, que agora os valores 0, 2 e 1 estão à frente de 3.
values = [3, 0, 2, 1, 8, 23, 7, 10, 77, 7]
E agora? Agora não há mais elementos menores ou iguais ao pivot para serem identificados. Todos os elementos menores ou iguais (0, 2 e 1) estão imediatamente à frente dele. Então, basta trocarmos o pivot (3) com o último deles (1).
values = [1, 0, 2, 3, 8, 23, 7, 10, 77, 7]
Feito. Agora 3 está em seu lugar, com todos os elementos menores ou iguais à sua esquerda e os elementos maiores à direita. Então, agora sabemos o que é e como funciona o particionamento. Chegou a hora de analisar o código.
Implementação do Particionamento de Lomuto editar
...
public static int partition(int[] values, int left, int right) {
int pivot = values[left];
int i = left;
for (int j = left + 1; j <= right; j++) {
if (values[j] <= pivot) {
i+=1;
swap(values, i, j);
}
}
// troca pivot (values[left]) com i.
swap(values, left, i);
return i;
}
...
Em primeiro lugar, vamos entender a assinatura do método particiona. Naturalmente, ele recebe como parâmetro o array a ser particionado. Recebe também dois índices válidos do array (left e right) que determinam os limites em que o algoritmo deve agir. Como o particionamento será usado dentro do contexto do Quick Sort, que é recursivo, precisamos controlar a faixa de valores em que o particiona será executado através destes índices. Claro, na primeira chamada, left = 0 e right = values.length - 1.
A primeira linha do método é a escolha do pivot. Estamos sempre escolhendo o elemento no primeiro índice como o pivot, por isso temos pivot = values[left].
Depois, lembre-se, precisamos iterar sobre o array procurando os elementos menores ou iguais e trocando-os com as posições à frente do pivot. Quem irá controlar a iteração é a variável j, enquanto i controla as trocas. Então, j varia sempre da segunda posição (left + 1), pois não precisamos comparar o pivot com ele mesmo, até a última posição do array (right). Enquanto isso, i começa na posição do pivot left e só é incrementado se um novo valor menor ou igual for encontrado.
Quando um valor menor ou igual ao pivot for encontrado (if values[j] <= pivot), efetuamos dois passos:
- Incrementar
i. - Trocar
values[i]porvalues[j]
Quando encerrar a iteração, basta agora trocar values[i] pela posição do pivot. Ou seja, trocamos values[i] por values[left].
Por fim, retornamos i, que é a posição final do pivot.
Quick Sort editar
Implementação editar
Você concorda que após uma execução do particiona o pivot está em sua posição na sequência? Isto é, se nossa missão for ordenar o array, não precisamos mais nos preocupar com o pivot, pois ele já está na posição correta. Precisamos, sim, nos preocupar com os elementos nos índices anteriores ao pivot, que estão no intervalo [left, i - 1] e com os elementos nos índices à frente do pivot, que estão no intervalo [i + 1, right].
O Quick Sort, então, é a execução de consectivos particionamentos. Efetua-se o primeiro levando em consideração todo o array (left = 0 e right = values.length - 1). Depois, leva-se em consideração a esquerda do pivot, ou seja, left = 0 e right = index_pivot - 1 e a direita do pivot (left = index_pivot + 1 e right = values.length - 1). Depois, o mesmo processo é feito com a esquerda e a direita dos novos pivots e assim por diante até que todo o array já tenha sido percorrido (left >= right).
public static void quickSort(int[] values, int left, int right) {
if (left < right) {
int index_pivot = partition(values, left, right);
quickSort(v, left, index_pivot - 1);
quickSort(v, index_pivot + 1, right);
}
}
Vamos analisar o estado abaixo para visualizar a execução do Quick Sort para o mesmo exemplo que estávamos abordando na seção anterior.
Após a execução do primeiro particionamento temos este estado:
values = [0left, 1, 2right, 3, 8left, 23, 7, 10, 77, 7right]
Note que há agora duas chamadas recursivas. Uma para a esquerda do pivot e outra para a direita do pivot. Cada chamada irá operar sobre os novos “lefts” e “rights”. Por isso o particiona recebe os índices em que deve executar a sua rotina. No exemplo acima, uma nova execução do particiona para a esquerda não irá alterar os valores porque eles já estão ordenados, mas a execução para a direita irá colocar o valor 10 em seu lugar e irá gerar uma nova rodada de duas execuções do particiona. De novo, esse processo acaba quando todas as verificações de left < right forem avaliadas com false.[1]
Análise do Tempo de Execução editar
Lembra dos passos para determinar o tempo de execução de algoritmos recursivos?. O primeiro passo é encontrar a relação de recorrência. O Quick Sort possui uma chamada ao método particiona e duas chamadas recursivas. Diferentemente do Merge Sort, as chamadas recursivas podem não dividir o array ao meio sempre, concorda? Isso vai depender de onde o pivot ficar depois do particiona. Se ele ficar ao meio, naturalmente teremos duas chamadas recursivas para T(n/2). Contudo, se ele ficar bem próximo ao início, por exemplo, teremos uma chamada recursiva para uma pequena porção à esquerda e uma chamada recursiva para uma porção bem maior (à direita). Então, por enquanto, vamos descrever a relação de recorrência como sendo o custo de particionar, somado ao custo da chamada para o array da esquerda e o custo da chamada para o array da direita:
T(n) = T(|left|) + T(|right|) + Θ(f(n))
Vamos deixar as coisas mais claras, pois sabemos calcular o tempo de execução do particiona. Se aplicarmos o que já aprendemos no material introdutório sobre análise é facil descobrir que o particiona é Θ(n), onde n é o tamanho do array, pois ele itera somente uma vez sobre todo o array. Então, podemos descrever a relação de recorrência do Quick Sort como:
T(n) = T(|left|) + T(|right|) + Θ(n)
Agora precisamos discutir os termos T(|left|) e T(|right|). Você já entende que o tamanho de left e right depende do índice em que o pivot fica após o particionamento. Vamos discutir o pior caso, primeiro.