Métodos de ordenação

quickSort

QuickSort
A idéia de ordenação
“O
cientista britânico da computação, Charles Antony Richard
Hoare, queria ordenar as palavras de um dicionário, tendo como objetivo principal, reduzir o problema original em problemas menores que poderiam ser solucionados de forma mais descomplicada e veloz.
Assim HOARE criou o QuickSort, um método de ordenação, que após uma série de melhorias foi publicado em 1962.”

QuickSort
A Estratégia
 Estratégia de divisão e conquista.

Como funciona?
 Divisão: Separamos elementos pequenos e grandes
 Conquista: Ordenamos cada parte (sub-lista)
Exemplo pivô central: pivô 21

QuickSort
A Lógica
1
2

• Verifica se o vetor está vazio

• Realiza escolha de um valor denominado pivô
• Separa o vetor em duas partes:

3

• 1ª Parte: Apenas elementos menores que o pivô
• 2ª Parte: Apenas elementos maiores que o pivô

4

• Recursivamente realiza a ordenação da sub-lista dos elementos menores e da sublista dos elementos maiores.

QuickSort

o Nas sub-listas após cada interação de recursividade pelo

menos um elemento é posto em sua posição final e não será mais manipulado na iteração seguinte.

Teste de Mesa

BubbleSort X QuickSort

Funcionamento

O Algoritmo package EstruturaDados; public class QuickSort { private int[] numeros; private int numero; public void organizar(int[] valores) {
// Verifica se o arra está vazio ou nulo if (valores == null || valores.length == 0) { return; } this.numeros = valores; numero = valores.length; quicksort(0, numero - 1);
}
private void quicksort(int menor, int maior) { int i = menor, j = maior;
// Seleciona o elemento de pivo do meio da lista int pivot = numeros[menor + (maior - menor) / 2];
// Divide em duas listas while (i pivot) { j--; }
// Se for encontrado algum valor na lista esquerda que é maior que
// o elemento pivô ou se for encontrado algum valor na lista