Introdução Ordenação e BubbleSort

Prévia do material em texto

Universidade Presbiteriana Mackenzie
Métodos de Ordenação: 
Introdução e o BubbleSort
Profa. Ana Cristina dos Santos
Faculdade de Computação e Informática
Linguagem de Programação I
1
Motivação
• O conceito de um conjunto ordenado de elementos
tem considerável impacto sobre nossa vida cotidiana.
• Exemplos:
– Localizar um número telefônico em catálogo;
– Identificar o CPF de um contribuinte;
– Procurar um livro em biblioteca tradicional ou virtual;
– Saber qual o próximo documento a ser impresso pela
impressora em um departamento da empresa;
– Saber qual o próximo processo a ser executado pelo
processador de uma máquina qualquer; etc...
2Introdução e BubbleSort
Definição
• Ordenar é o processo de reorganizar um conjunto de
objetos em um ordem ascendente ou descendente,
segundo algum critério.
• O objetivo da ordenação ou classificação é facilitar a
recuperação posterior de itens do conjunto ordenado.
• A maioria dos métodos de ordenação é baseada em 
comparações das chaves.
3Introdução e BubbleSort
Notação
• Os algoritmos trabalham sobre os registros de um 
arquivo.
• Cada registro possui uma chave utilizada para controlar 
a ordenação.
• Podem existir outros componentes em um registro.
• Qualquer tipo de chave sobre o qual exista uma regra de 
ordenação bem definida pode ser utilizado.
• A maioria dos métodos de ordenação é baseada em 
comparações das chaves. 
• Existem métodos de ordenação que utilizam o princípio 
da distribuição.
4Introdução e BubbleSort
Classificação
Os algoritmos de ordenação podem ser:
• Ordenação interna: se os registros a serem ordenados estiverem 
na RAM, qualquer registro pode ser imediatamente acessado.
• Ordenação externa: se os registros a serem ordenados estiverem 
em armazenamento auxiliar (disco), em que os registros são 
acessados sequencialmente ou em grandes blocos.
5Introdução e BubbleSort
Estabilidade
Os algoritmos de ordenação podem ser:
• Um método de ordenação é estável se a ordem relativa 
dos itens com chaves iguais não se altera durante a 
ordenação.
• Alguns dos métodos de ordenação mais eficientes não 
são estáveis.
• A estabilidade pode ser forçada quando o método é 
não-estável.
6Introdução e BubbleSort
Estabilidade
Exemplo:
• Se uma lista alfabética de nomes de funcionários de 
uma empresa é ordenada pelo campo salário, então um 
método estável produz uma lista em que os 
funcionários com o mesmo salário aparecem em ordem 
alfabética
7Introdução e BubbleSort
Ordenação Interna
• Métodos simples:
– Adequados para pequenos arquivos.
– Requerem O(n2) comparações.
– Produzem programas pequenos.
• Métodos eficientes:
– Adequados para arquivos maiores.
– Requerem O(n log n) comparações.
– Usam menos comparações.
– As comparações são mais complexas nos detalhes.
– Métodos simples são mais eficientes para pequenos 
arquivos.
8Introdução e BubbleSort
Métodos de Ordenação Interna
• Métodos simples:
– Bolha (BubbleSort)
– Seleção do Mínimo ou do Máximo (Selection Sort)
– Inserção Direta (Insertion Sort)
• Métodos eficientes:
– Quicksort
– Mergesort
9Introdução e BubbleSort
Análise de Desempenho
• A eficiência de tempo é calculada pelo número de
operações críticas efetuadas.
• Operações críticas:
 comparação entre chaves
 movimentação de registros ou de ponteiros para
registros
 troca de dois registros
10Introdução e BubbleSort
Categorias Métodos de Ordenação
• Classificação por Trocas
– Bolha (BubbleSort)
– QuickSort
• Classificação por Seleção
– Seleção do Mínimo ou do Máximo
• Classificação por Inserção
– Inserção Direta
• Classificação por Intercalação
– MergeSort
11Introdução e BubbleSort
Principais Categorias de Métodos
– Classificação por Trocas
– Classificação por Seleção
– Classificação por Inserção
– Classificação por Intercalação
12Introdução e BubbleSort
Classificação por Trocas
• Caracteriza-se pela comparação aos pares de chaves,
trocando-as de posição caso estejam fora de ordem
no par.
• Principais algoritmos
– BubbleSort (Bolha)
– QuickSort
13Introdução e BubbleSort
Convenção
• Veremos alguns algoritmos e técnicas de ordenação. Cada 
um apresenta diferentes soluções para o mesmo 
problema: ordenar um conjunto de dados. 
• Devido a essa variedade de soluções e complexidades, eles 
podem ter variações no desempenho. Porém, cabe agora, 
estudar apenas essas soluções.
• Por convenção, consideraremos vetores de números, ao 
invés de registros. Porém, sabe-se que, esses números 
estariam representados as chaves dos registros 
armazenados em uma tabela. 
• Essa convenção facilita o entendimento das soluções 
apresentadas.
14Introdução e BubbleSort
15
Especificação do Problema
• Dado um conjunto com N elementos do mesmo tipo 
de dado armazenados em um vetor V, rearranjar os 
elementos do vetor de forma que seus elementos 
fiquem ordenados, em ordem crescente ou 
decrescente
Introdução e BubbleSort
16
Método Bolha ou BubbleSort
• Mais lento
• Mais simples conceitualmente
• Funciona através da comparação de 
elementos dois a dois, percorrendo a 
estrutura toda até que esteja ordenado
Introdução e BubbleSort
17
Método Bolha - Estratégia
• Em cada iteração, 
– “Borbulhar” o maior elemento para o final do vetor,
– Percorrendo o vetor da primeira posição até a final (da 
esquerda para a direita).
– Comparando pares de elementos consecutivos, 
trocando de lugar os que estão fora de ordem
– O final da porção não ordenada do vetor diminui a cada 
vez que um elemento máximo chega ao fim
Introdução e BubbleSort
Iteração 1 – Levar o maior elemento para o fim do vetor
43210
1a Iteração
2550803060
25508060302a Iteração
25508060303
a Iteração
4a Iteração
2580506030
8025506030
18Introdução e BubbleSort
8025605030
8025506030
Iteração 2 – Levar o maior elemento para o fim do vetor
43210
8025506030
1a Iteração
2a Iteração
3a Iteração
8060255030
19Introdução e BubbleSort
8060502530
8060255030
Iteração 3 – Levar o maior elemento para o fim do vetor
43210
8060255030
1a Iteração
2a Iteração
20Introdução e BubbleSort
43210
8060502530
Iteração 4 – Levar o maior elemento para o fim do vetor
1a Iteração
8060503025
21Introdução e BubbleSort
22
Desempenho do BubbleSort
• Quantas iterações tenho que fazer?
– Em cada iteração, quantas comparações dois a 
dois são feitas?
– No final de cada iteração, qual o resultado?
Introdução e BubbleSort
Desempenho do BubbleSort
• Melhor caso
Quando o vetor já se encontra ordenado  nenhuma troca
ocorre na primeira varredura.
Custo linear: n - 1 comparações
• Pior caso
Quando o vetor se encontra na ordem inversa a desejada.
A cada varredura apenas uma chave será colocada em sua
posição definitiva.
23Introdução e BubbleSort
Desempenho do BubbleSort
• Pior caso
Qtd de Comparações Trocas
Iterações efetuadas efetuadas
1 n - 1 n - 1
2 n - 2 n - 2
3 n - 3 n - 3
... ... ...
n - 1 1 1
( n2 - n )/2 ( n2 - n )/2
Cmédio = ( Cpior + Cmelhor ) / 2
= (( n2 - n ) / 2 )+ ( n - 1 ))/ 2
= ( n2 + n - 2 ) / 4
O (n2)
Total: ( n2 - n )/2 = O (n2)
24Introdução e BubbleSort
Método BubbleSort
public void bubbleSort (int [] v){
for (int i = 0; i < v.length -1 ; i++)
for (int j = 0; i < v.length-1-i ; j++)
if (v[j] > v[j+1])
troca (v, j, j+1);
}
public void troca ( int[] v, int i, int j){
int temp = v[i];
v[i] = v[j];
v[j] = temp;
}
25Introdução e BubbleSort
26
Sobrecargapublic void bubbleSort (int[] v){
bubbleSort (v, v.length);
}
Introdução e BubbleSort
Invocando o Método bubbleSort
public static void main(String[] args){
int[] v;
v = new int[50];
…
package.Sort.bubbleSort(v);
...
}
27Introdução e BubbleSort
Invocando o Método bubbleSort
import package.*;
public static void main(String[] args){
int[] v;
v = new int[50];
Sort.bubbleSort(v,n);
...
}
28Introdução e BubbleSort
Invocando o Método bubbleSort
import static package.Sort.*;
public static void main (String[] args){
int[] v;
v = new int[50];
bubbleSort(v,n);
...
}
29Introdução e BubbleSort
Método BubbleSort
Método da Bolha Melhorado: Termina execução quando nenhuma 
troca é realizada após uma passada pelo vetor
public void bubbleSort (int [] v){
boolean flag=true;
for (int i = 0; i < (v.length -1)&&(flag==true) ; i++){ 
flag=false;
for (int j = 0; i < v.length-1-i ; j++)
if (v[j] > v[j+1]){
troca (v, j, j+1);
flag=true;
}
}
}
30Introdução e BubbleSort
Exercícios
• Faça um teste de execução do método de ordenação bolha para:
– V={30, 40, 50, 20,10}
• Construa o método main que leia dados para um vetor com n 
elementos e os ordena.
• Quantas operações críticas (comparações + trocas) foram 
necessárias ?
• Quantas varreduras são necessárias para detectar que o vetor 
acima está classificado ?
• Informe a complexidade do algoritmo BubbleSort nos casos: 
Melhor, Pior e Caso Médio.
31Introdução e BubbleSort
Algoritmos Animados - Sites
http://www.csse.monash.edu.au/~dwa/Anima
tions/index.html
http://math.hws.edu/TMCM/java/xSortLab/
32Introdução e BubbleSort