Ordenação de Dados

Prévia do material em texto

Estrutura de Dados 1
UNIP - Ciência da Computação e Sistemas de Informação
Estrutura de Dados
AULA 9
Ordenação de Dados
Estrutura de Dados 2
Ordenação de Dados 
• Processo bastante utilizado na 
computação de uma estrutura de dados
• Dados ordenados garantem uma melhor 
performance de pesquisa a uma ED.
Estrutura de Dados 3
Compromisso
“A complexidade da ordenação da ED não deve 
exceder a complexidade da computação a ser 
feita na ED sem o processo de ordenação”
• Exemplo: deseja-se realizar uma única pesquisa 
a um vetor:
– busca seqüencial  O(n)
– ordenação  O(n log n)
– Não vale a pena ordenar!
Estrutura de Dados 4
Métodos de Ordenação
• Ordenação por troca
– BubbleSort (método da bolha)
– QuickSort (método da troca e partição)
• Ordenação por inserção
– InsertionSort (método da inserção direta)
– BinaryInsertionSort (método da inserção direta binária)
• Ordenação por seleção
– SelectionSort (método da seleção direta)
– HeapSort (método da seleção em árvore)
• Outros métodos
– MergeSort (método da intercalação)
– BucketSort (método da distribuição de chave)
Métodos de 
Ordenação Simples 
Estrutura de Dados 5
Métodos de Ordenação Simples 
• Características:
– fácil implementação
– alta complexidade
– comparações ocorrem sempre entre 
posições adjacentes do vetor (estático ou 
dinâmico)
Estrutura de Dados 6
Métodos de Ordenação 
• Vamos apresentar 3 métodos:
– Bubble Sort
– Insertion Sort
– Quick Sort
Fonte: http://partilho.com.br/java-netbeans/ordenacao-em-java-metodos-programar/
Estrutura de Dados 7
Bubble Sort
• O bubble sort, ou ordenação por flutuação 
(literalmente "por bolha"), é um algoritmo de 
ordenação dos mais simples. A ideia é 
percorrer o vetor diversas vezes, a cada 
passagem fazendo flutuar para o topo o maior 
elemento da sequência. Essa movimentação 
lembra a forma como as bolhas em um tanque 
de água procuram seu próprio nível, e disso 
vem o nome do algoritmo.
Estrutura de Dados 8
Bubble Sort
• No melhor caso, o algoritmo executa n 
operações relevantes, onde n representa o 
número de elementos do vetor. No pior caso, 
são feitas n^2 operações. A complexidade 
desse algoritmo é de Ordem quadrática. Por 
isso, ele não é recomendado para programas 
que precisem de velocidade e operem com 
quantidade elevada de dados.
Estrutura de Dados 9
Bubble Sort
• O método bubble sort trabalha comparando todos os 
valores dos vetores, por exemplo o primeiro com o 
segundo depois com o terceiro, e assim por diante até 
o último valor, depois ele inicia o mesmo processo só 
que uma posição a mais comparando o segundo com 
o primeiro, depois com o terceiro. A ideia é a de que 
os valores maiores ou mais “pesados” vão descendo 
enquanto os mais leves ficam em cima e, por isso, é 
chamado de método bolha. Esse processo de 
comparação passa por uma condição que se um valor 
for menor que o outro eles trocam de posição.
Estrutura de Dados 10
Bubble Sort
int[] vet = {8, 19, 31, 25, 1};
int aux = 0;
int i = 0;
System.out.println("Vetor desordenado: ");
for (i = 0; i < 5; i++) {
System.out.println(" " + vet[i]);
}
System.out.println(" ");
for (i = 0; i < 5; i++) {
for (int j = 0; j < 4; j++) {
if (vet[j] > vet[j + 1]) {
aux = vet[j];
vet[j] = vet[j + 1];
vet[j + 1] = aux;
}
}
}
System.out.println("Vetor organizado:");
for (i = 0; i < 5; i++) {
System.out.println(" " + vet[i]);
}
Estrutura de Dados 11
InsertionSort
• Insertion sort, ou ordenação por inserção, é um 
simples algoritmo de ordenação, eficiente quando 
aplicado a um pequeno número de elementos. Em 
termos gerais, ele percorre um vetor de elementos 
da esquerda para a direita e à medida que avança 
vai deixando os elementos mais à esquerda 
ordenados. O algoritmo de inserção funciona da 
mesma maneira com que muitas pessoas 
ordenam cartas em um jogo de baralho como o 
pôquer. Esse algoritmo se baseia no processo de 
inserção, dessa forma quando ele recebe um 
novo valor ele sempre vai o alocar na posição que 
corresponde a sua faixa de ordenação.
Estrutura de Dados 12
InsertionSort
int element[] = {22, 9, 7, 6, 1, 49, 35, 3, 0};
int chave, i;
System.out.print("Lista Original: ");
for (int x = 0; x < element.length; x++){
System.out.print(element[x] + ", ");}
for (int j = 1; j < element.length; j++) {
chave = element[j];
i = j - 1;
while (i >= 0 && element[i] > chave) {
element[i + 1] = element[i];
i = i - 1;
}
element[i + 1] = chave;}
System.out.print("\nLista reordenada: ");
for (int j = 0; j < element.length; j++) {
System.out.print(element[j] + ", ");}
Estrutura de Dados 13
QuickSort
• O algoritmo Quicksort é um método de 
ordenação muito rápido e eficiente, inventado 
por C.A.R. Hoare em 1960, quando visitou a 
Universidade de Moscovo como estudante. 
Naquela época, Hoare trabalhou em um projeto 
de tradução de máquina para o National
Physical Laboratory. Ele criou o 'Quicksort ao 
tentar traduzir um dicionário de inglês para 
russo, ordenando as palavras, tendo como 
objetivo reduzir o problema original em 
subproblemas que possam ser resolvidos mais 
facil e rapidamente. 
Estrutura de Dados 14
QuickSort
• A medida que o vetor vai sendo ordenado vão 
sendo realizadas partições recursivas com 
objetivo de ganhar desempenho.
Estrutura de Dados 15
QuickSort
public class TestaQuick {
public static int[] vetor = {56, 446, 389, 18, 446, 17, 
493, 186, 455, 94, 374, 119, 81, 250, 496, 84, 129, 73, 
414, 156, 199, 84, 17, 16, 56};
public static void main(String[] args) {
System.out.print("Vetor de Entrada: ");
imprime(vetor);
quick_sort(vetor,0, vetor.length - 1);
System.out.print("\nVetor Ordenado: ");
imprime(vetor);
System.exit(0);
}
Estrutura de Dados 16
QuickSort
public static void imprime(int[] aux) {
for (int i = 0; i < vetor.length; i++) {
System.out.print(" " + aux[i]);
}
}
public static void quick_sort(int[] v, int ini, int
fim) {
int meio;
if (ini < fim) {
meio = partition(v, ini, fim);
quick_sort(v, ini, meio);
quick_sort(v, meio + 1, fim);
}
}
Estrutura de Dados 17
QuickSort
public static int partition(int[] v, int ini, int fim) {
int pivo, topo, i;
pivo = v[ini];
topo = ini;
for (i = ini + 1; i <= fim; i++) {
if (v[i] < pivo) {
v[topo] = v[i];
v[i] = v[topo + 1];
topo++;
}
}
v[topo] = pivo;
return topo;
}
}