Métodos de ordenação

316 palavras 2 páginas
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

Relacionados

  • Métodos de Ordenação
    318 palavras | 2 páginas
  • Método de Ordenação
    554 palavras | 3 páginas
  • Métodos de Ordenação
    10225 palavras | 41 páginas
  • métodos de ordenação
    1462 palavras | 6 páginas
  • métodos de ordenação
    2226 palavras | 9 páginas
  • Métodos de ordenação
    1655 palavras | 7 páginas
  • Metodos de ordenação
    678 palavras | 3 páginas
  • Métodos de ordenação
    909 palavras | 4 páginas
  • Métodos de ordenação
    747 palavras | 3 páginas
  • Metodos de Ordenacao
    8212 palavras | 33 páginas