UNIP - Ciência da Computação e Sistemas de Informação
Estrutura de Dados
AULA 9
Ordenação de Dados
Estrutura de Dados
1
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
2
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
3
Métodos de Ordenação
Métodos de
Ordenação Simples
• 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)
Estrutura de Dados
4
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
5
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
6
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
7
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
8
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
9
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
10
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
11
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
12
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
13
QuickSort
• A medida que o vetor vai sendo ordenado vão
sendo realizadas partições recursivas com
objetivo de ganhar desempenho.
Estrutura de Dados
14
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
15
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
16
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;
}
}
Estrutura de Dados
17