Estruturas de Dados - Classificação

Prévia do material em texto

CIC/UnB - Estruturas de 
dados
Classificação
Caracterização do 
problema
● A classificação é um dos problemas mais 
explorados e conhecidos na computação
● Está fortemente relacionado com a busca
● P. ex., como achar um livro em uma 
biblioteca sem uma ordenação?
Nomenclatura
● Arquivo: coleção r[0], r[1], ... de itens
● Registro: os itens de um arquivo
● Chave: subcampo de um registro usado 
como referência para classificação
● Às vezes a chave não está dentro do 
registro
Nomenclatura
● A classificação pode ser feita por mais de 
uma chave. Nesse caso às chaves são 
designadas prioridades e as de menor 
prioridade servem para desempatar a 
classificação quando as de maior são 
iguais. 
● Isso equivale a uma classificação da 
concatenação das chaves:
 
 chave1.chave2.chave3... 
Nomenclatura
● Diz-se que um arquivo está classificado 
por uma chave se para r[i] e r[j] valer:
i < j implica k[i] < k[j] 
● Quando existem chaves iguais em 
registros diferentes, vale:
i < j implica k[i] <= k[j] 
● Uma classificação que mantém mesma 
ordem dos registros iguais no arquivo 
original é dita estável
Nomenclatura
● A classificação é dita interna quando os 
registros estão na memória principal e 
externa quando estão em algum 
dispositivo auxiliar (disco)
● Nosso foco principal é a classificação 
interna. Na classificação externa, o que 
se faz é segmentar o arquivo em pedaços 
que caibam na memória principal e 
depois promover a intercalação (merge) 
das partes.
Nomenclatura
● Nem sempre é preciso ordenar o arquivo:
Arquivo Classificado Arquivo Original Arquivo ponteiros
Chave Outros Campos Chave Outros Campos Ordem Ponteiro
 1 AAAA 4 DDDD 1 3
 2 BBBB 2 BBBB 2 2
 3 CCCCC 1 AAAAA 3 5
 4 DDDD 5 EEEEE 4 1
 5 EEEEE 3 CCCCC 5 4
(quando o volume de dados é grande, cria-se um arquivo de ponteiros...)
Eficiência
● Existem muitos métodos de classificação 
e busca, uns mais ou menos complexos, 
mais ou menos eficiente
● Geralmente, os mais simples são menos 
eficientes
● A escolha depende de muitos fatores: 
tempo de codificação, tempo de 
execução, espaço necessário, entre outros
Eficiência
● Um fator importante diz respeito à 
proporcionalidade. Por exemplo, certo 
método pode ser rápido para arquivos 
pequenos, mas o tempo de execução 
crescerá muito, de modo não proporcional 
à medida em que o volume de dados 
crescer.
● Os métodos que guardam essa proporção 
são ditos proporcionais.
Eficiência
● Avalia-se a eficiência de um método 
observando-se as operações críticas que 
ele executa (por exemplo, comparações 
entre chaves ou trocas de dois registros, 
movimentação de ponteiros de registros).
● Normalmente tenta-se analisar o 
algorítmo e identificar uma fórmula que 
produz o “tempo“ médio esperado para a 
classificação de n registros
Eficiência
● Esse “tempo“ nem sempre será dado em segundos, mas em 
uma unidade de tempo esperada para a classificação de “um“ 
registro. Assim surge uma função denominada ordem, usada 
para classificar a eficiência de um algorítmo.
● Diz-se, por exemplo, que certo algorítmo é da ordem de n - 
O(n) – se seu tempo de classificação é proporcional à 
quantidade de registros; ou que é da ordem de n2 - O(n2) – se 
seu tempo de classificação cresce de acordo com o quadrado 
do número de registros a serem ordenados.
● Algoritmo O(n):
 se n = 100, tempo = 100; se n=1000 tempo = 1000
● Algoritmo O(n2): 
 se n = 100 tempo = 10.000; se n=1000 tempo=1.000.000
Eficiência
● Antes de nos aprofundarmos nas 
verificações de eficiência, vamos 
investigar os algorítmos de classificação 
mais conhecidos e observar a sua 
avaliação
● O método mais simples e conhecido é 
denominado método da seleção.
Método da seleção
● Esse método seleciona os elementos um a 
um e os compara com os demais, fazendo 
trocas de posição quando necessário
● No primeiro passo é selecionada a 
primeira posição do conjunto – o seu 
elemento é comparado com o segundo, 
terceiro e assim sucessivamente, sendo 
trocado sempre que for preciso 
Método da seleção
● Ao fim do primeiro passo, ficará na 
primeira posição o elemento de menor 
valor:
8 6 6 6 3
6 8 8 8 8
7 7 7 7 7
9 9 9 9 9
3 3 3 3 6
Método da seleção
● Ao fim do segundo passo, ficará na 
segunda posição o segundo menor valor:
3 3 3 3 3
8 7 7 7 6
7 8 8 8 8
9 9 9 9 9
6 6 6 6 7
Método da seleção
● E assim por diante...
● O método, embora simples, não parece 
muito inteligente nem eficiente.
● Ele não possui sensibilidade ao contexto e 
sempre fará n-1 passos, sendo que em 
cada passo faz menos comparações.
● O método mostrado a seguir é mais 
interessante.
Método da Bolha
● Para explicar esse método, usaremos 
apenas um vetor x[n] com n números 
inteiros, que devem ser ordenados de 
modo que x[i] <= x[j] para 0<=i<j<n
● O método sugere que sejam feitas várias 
passagens pelo vetor, sempre trocando o 
elemento (i) pelo elemento (i+1) para 
0<=i <n-1, quando necessário.
Método da Bolha
● Vamos exemplificar: 
ii 00 11 22 33 44 55 66 77 troca?troca?
0 25 57 48 37 12 92 86 33 não
1 25 57 48 37 12 92 86 33 sim
2 25 48 57 37 12 92 86 33 sim
3 25 48 37 57 12 92 86 33 sim
4 25 48 37 12 57 92 86 33 não
5 25 48 37 12 57 92 86 33 sim
6 25 48 37 12 57 86 92 33 sim
7 25 48 37 12 57 86 33 92 < fim primeira iteração
Método da Bolha
● Vamos exemplificar: 
ii 00 11 22 33 44 55 66 77 troca?troca?
0 25 48 37 12 57 86 33 92 não
1 25 48 37 12 57 86 33 92 sim
2 25 37 48 12 57 86 33 92 sim
3 25 37 12 48 57 86 33 92 não
4 25 37 12 48 57 86 33 92 não
5 25 37 12 48 57 86 33 92 sim
6 25 37 12 48 57 33 86 92 < fim segunda iteração
Método da Bolha
● Vamos exemplificar: 
ii 00 11 22 33 44 55 66 77 troca?troca?
0 25 37 12 48 57 33 86 92 não
1 25 37 12 48 57 33 86 92 sim
2 25 12 37 48 57 33 86 92 não
3 25 12 37 48 57 33 86 92 não
4 25 12 37 48 57 33 86 92 sim
5 25 12 37 48 33 57 86 92 < fim terceira iteração
Método da Bolha
● Vamos exemplificar: 
ii 00 11 22 33 44 55 66 77 troca?troca?
0 25 12 37 48 33 57 86 92 sim
1 12 25 37 48 33 57 86 92 não
2 12 25 37 48 33 57 86 92 não
3 12 25 37 48 33 57 86 92 sim
4 12 25 37 33 48 57 86 92 < fim quarta iteração
Método da Bolha
● Vamos exemplificar: 
ii 00 11 22 33 44 55 66 77 troca?troca?
0 12 25 37 33 48 57 86 92 não
1 12 25 37 33 48 57 86 92 não
2 12 25 37 33 48 57 86 92 sim
3 12 25 33 37 48 57 86 92 < fim quinta iteração
Método da Bolha
● Vamos exemplificar: 
ii 00 11 22 33 44 55 66 77 troca?troca?
0 12 25 33 37 48 57 86 92 não
1 12 25 37 37 48 57 86 92 não
3 12 25 33 37 48 57 86 92 < fim sexta iteração
Como não houve mais troca, podemos encerrar e considerar o conjunto ordenado!!