Ordenação de Dados - Quick Sort • Universidade Java
Ordenação de Dados - Quick Sort
Conceitos do QuickSort
O próximo algoritmo de ordenação de dados que falaremos é o Quick Sort. Assim como o Merge Sort, o Quick Sort é um algoritmo que se baseia no princípio da divisão e conquista, porem ele trabalha de maneira contrária uma vez que a parte mais pesada do algoritmo acontece antes da recursão e não nela.
O algoritmo Quick Sort trabalha ordenando uma sequência qualquer de valores dividindo-a em subsequências menores, aplicando recursão para ordenar cada uma destas subsequências e por fim, concatenando-as novamente em uma sequência idêntica a original, porem, já ordenada.
Divisão – Para uma sequência S de ao menos dois elementos, basta escolher um elemento x de S chamado por pivô. Uma vez feito isso, removemos todos os elementos de S e os alocamos em três novas subsequências, sendo elas:
Uma subsequência Me, composta de elementos menores do que x.
Uma subsequência Ig, composta de elementos iguais a x.
Uma subsequência Ma, composta de elementos maiores do que x.
Vale lembrar que, caso exista apenas um elemento de valor igual ao de x, a subsequência Lg será composta de apenas um elemento.
Recursão – Ordene as sequências Me e Ma recursivamente.
Conquista – Recoloque os elementos das subsequências Me, Ig e Ma novamente na sequência S nesta mesma ordem em que foram mencionados.
Uma das melhores maneiras de se aplica o Quick Sort, é através da metodologia Quick Sort in-place. É dito in-place, pois não necessitará de novas sequências, ou seja, não necessita alocar mais memória.
Para que isto seja possível, iremos no preocupar não somente com a composição de novos vetores, mas sim iremos a partir do pivô comparar todos os elementos do vetor com o pivô de maneira a trocar elementos de posição e deixar o pivô centralizado, ou seja, com elementos menores que ele a sua esquerda e maiores que ele a sua direita, com isso já teremos os três novos vetores.
Para que isso seja possível, adotaremos a seguinte técnica:
Escolher um elemento x do vetor, no caso o primeiro elemento do vetor;
Percorrer o vetor da esquerda para a direita procurando um elemento maior que x, e da direita para a esquerda procurando um elemento menor ou igual a x. Quando este elementos forem encontrados, devemos troca-los de posição;
Trocar x com o j-ésimo elemento e devolver a posição j.
x = S[p] = 12
4 < 12? Sim -> incrementar ponteiro…
15 < 12? Não! -> parar ponteiro…
28 > 12? Sim -> decrementar ponteiro…
20 > 12? Sim -> decrementar ponteiro…
6 > 12? Não! -> parar ponteiro…
Os dois ponteiros pararam, logo os seus elementos devem ser trocados e ambos os ponteiros devem ser incrementados!
7 < 12? Sim -> incrementar ponteiro…
10 < 12? Sim -> incrementar ponteiro…
2 < 12? Sim -> incrementar ponteiro…
1 < 12? Sim -> incrementar ponteiro…
13 < 12? Não! -> parar ponteiro…
13 > 12? Sim -> decrementar ponteiro…
1 > 12? Não! -> parar ponteiro…
Uma vez que os dois ponteiros se ultrapassaram, o elemento escolhido x deve ser agora trocado com o elemento da posição j.
Essa foi a primeira passada percorrendo o vetor, o mesmo processo deve continuar até que o vetor fique completamente ordenado. O código a seguir apresenta como implementar o Quick Sort em Java.
Implementação do QuickSort in-place em Java
Para iniciar o exemplo, vamos criar uma classe QuickSort:
* Classe utilizada para demonstrar o uso do algoritmo de ordenação
* Quick Sort.
* Método para a ordenação de um vetor de inteiros.
* @param vetor - Vetor de inteiros que sera ordenado.
public void ordenarVetorDeInteiros(int[] vetor) {
quickSort(vetor, 0, vetor.length - 1);
A classe QuickSort já disponibiliza um método específico para a ordenação de números inteiros, conforme a linha 15 do código.
Note que este método invoca o método private void quickSort(int[] vetor, int inicio, int fim), logo vamos a seu código fonte:
* Método que irá chamar a divisão do vetor nos três vetores do conceito.
* Na realidade o vetor do meio esta sendo incarado apenas como o elemento
* pivô retornado pelo método dividir.
* @param vetor - Vetor de inteiros que passara pelo Quick Sort.
* @param inicio - Indice inicial do vetor que sera considerado no Quick Sort.
* @param fim - Indice final do vetor que sera considerado no Quick Sort.
private void quickSort(int[] vetor, int inicio, int fim) {
if(fim > inicio) {
//Chamada da rotina que ira dividir o vetor em 3 partes.
int indexPivo = dividir(vetor, inicio, fim);
/* Chamada recursiva para redivisao do vetor de elementos menores
que o pivô. */
quickSort(vetor, inicio, indexPivo - 1);
/* Chamada recursiva para redivisao do vetor de elementos maiores
quickSort(vetor, indexPivo + 1, fim);
Observe que nesta etapa, o algoritmo visa divider o vetor de entrada utilizando o método private int dividir(int[] vetor, int inicio, int fim), conforme a linha 32. Nesta etapa de divisão veremos como o algoritmo se comporta para realizar a ordenação a cada etapa desta divisão.
* Método que ira dividir o vetor e encontrar o indice do pivô.
* @param vetor - Vetor de inteiros
* @param inicio - Indice inicial do vetor.
* @param fim - Indice final do vetor.
* @return O indice do pivo.
private int dividir(int[] vetor, int inicio, int fim) {
int pivo, pontEsq, pontDir = fim;
pontEsq = inicio + 1;
pivo = vetor[inicio];
while(pontEsq <= pontDir) {
/* Vai correr o vetor ate que ultrapasse o outro ponteiro
ou ate que o elemento em questão seja menor que o pivô. */
while(pontEsq <= pontDir && vetor[pontEsq] <= pivo) {
pontEsq++;
que o elemento em questão seja maior que o pivô. */
while(pontDir >= pontEsq && vetor[pontDir] > pivo) {
pontDir--;
/* Caso os ponteiros ainda nao tenham se cruzado, significa que valores
menores e maiores que o pivô foram localizados em ambos os lados.
Trocar estes elementos de lado. */
if(pontEsq < pontDir) {
trocar(vetor, pontDir, pontEsq);
trocar(vetor, inicio, pontDir);
return pontDir;
Este trecho de código responsável pela divisão do vetor em função da comparação por base de um vetor, estabelecido pelo elemento inicial do vetor, conforme a linha 63.
Utilizando dois ponteiros, um vindo da esquerda e outro da direita, este algoritmo ao mesmo que divide o vetor em dois novos vetores, estabelece uma ordenação fundamentada no pivô, onde os elementos menores que ele ficarão a sua esquerda e os maiores a sua direita. Quando elementos que não atendam a esta regra são localizados no vetor, estes são trocados pelo método private void trocar(int[] vetor, int i, int j), conforme linhas 79 e 84. Vejamos seu código fonte:
* Método para trocar dois elementos de um vetor.
* @param vetor - Vetor de inteiros que tera seus elementos trocados.
* @param i - Indice do elemento que sera trocado.
* @param j - Indice do elemento que sera trocado.
private void trocar(int[] vetor, int i, int j) {
int temp = vetor[i];
vetor[j] = temp;
Agora, já finalizada a classe QuickSort, vamos elaborar uma classe de teste para ver o comportamento do algoritmo: