Embed Size (px)
Citation preview
Ordenação (Parte 1) Prof. Túlio Toffolo http://www.toffolo.com.br
BCC202 – Aula 13
Algoritmos e Estruturas de Dados I
Critério de Ordenação
• Ordena-se de acordo com uma chave:
typedef int TChave; typedef struct { TChave Chave; /* outros componentes */ } TItem;
2
Características
• Estabilidade: relativo à manutenção da ordem original de itens de chaves iguais
• Ordenação interna: dados a serem ordenados cabem todos na memória principal.
• Princípio: comparação x distribuição
3
Critério de Avaliação
• Sendo n o número de registros no arquivo, as medidas de complexidade relevantes são:
• Número de comparações C(n) entre chaves.
• Número de movimentações M(n) de itens
4
Outras Considerações
• O uso econômico da memória disponível é um requisito primordial na ordenação interna.
• Métodos de ordenação in situ são os preferidos.
• Métodos in situ não utilizam memória adicional.
• Métodos que utilizam listas encadeadas não são muito utilizados.
• Métodos que fazem cópias dos itens a serem ordenados possuem menor importância.
5
Métodos
• Métodos a que estudaremos hoje:
• Bolha (BubbleSort)
• Seleção (SelectSort)
• Inserção (InsertSort)
6
ORDENAÇÃO DA BOLHA
BUBBLESORT
Método Bolha
• Os elementos vão “borbulhando” a cada iteração do método até a posição correta para ordenação da lista
• O método poderia parar quando nenhum elemento borbulhace/trocasse de posição
• Como os elementos são trocados (borbulhados) frequentemente, há um alto custo de troca de elementos
8
void Bolha (TItem* v, int n) { int i, j; TItem aux; for (i = 0; i < n-1; i++) { for (j = 1; j < n-i; j++) { if (v[j].Chave < v[j-1].Chave) { aux = v[j]; v[j] = v[j-1]; v[j-1] = aux; } } }}
Método Bolha
9
Análise de Complexidade
M (n) = 3C(n) =O(n2 )
• Comparações – C(n)
• Movimentações – M(n)
)(2
)1(2
)1)(20()1(
1)1()(
22
2
0
2
0
2
0
2
0
nOnn
nnnnn
ininnCn
i
n
i
n
i
n
i
=−
=
−−−−+
−−=
−−=−−= ∑∑∑∑−
=
−
=
−
=
−
=
10
Ordenação por Bolha
• Vantagens:
• Algoritmo simples
• Algoritmo estável
• Desvantagens:
• O fato de o arquivo já estar ordenado não ajuda reduzir o número de comparações (o custo continua quadrático), porém o número de movimentação cai a zero.
• Possível modificação na atual implementação?
11
void Bolha (TItem* v, int n) { int i, j; TItem aux; for (i = 0; i < n-1; i++) { for (j = 1; j < n-i; j++) { if (v[j].Chave < v[j-1].Chave) { aux = v[j]; v[j] = v[j-1]; v[j-1] = aux; } } }}
Método Bolha
12
void Bolha (TItem* v, int n) { int i, j, troca; TItem aux; for (i = 0; i < n-1; i++) { troca = 0; for (j = 1; j < n-i; j++) { if (v[j].Chave < v[j-1].Chave) { aux = v[j]; v[j] = v[j-1]; v[j-1] = aux; troca++; } } if (troca == 0) break; }}
Método Bolha – Melhoria!!!
13
ORDENAÇÃO POR SELEÇÃO
SELECTSORT
Método Seleção
• Seleção do n-ésimo menor (ou maior) elemento da lista
• Troca do n-ésimo menor (ou maior) elemento com a n-ésima posição da lista
• Uma única troca por vez é realizada
15
void Selecao (TItem* v, int n) { int i, j, Min; TItem aux; for (i = 0; i < n - 1; i++) { Min = i; for (j = i + 1 ; j < n; j++) if (v[j].Chave < v[Min].Chave) Min = j; aux = v[Min]; v[Min] = v[i]; v[i] = aux; }}
Método Seleção
16
Análise de Complexidade
)(2
)1(2
)1)(20()1(
1)1()(
22
2
0
2
0
2
0
2
0
nOnn
nnnnn
ininnCn
i
n
i
n
i
n
i
=−
=
−−−−+
−−=
−−=−−= ∑∑∑∑−
=
−
=
−
=
−
=
• Comparações – C(n)
• Movimentações – M(n)
M (n) = 3(n−1) =O(n)
17
Ordenação por Seleção
• Vantagens:
• Custo linear no tamanho da entrada para o número de movimentos de registros.
• É o algoritmo a ser utilizado para arquivos com registros muito grandes (alto custo de movimentação).
• É muito interessante para arquivos pequenos.
• Desvantagens:
• O fato de o arquivo já estar ordenado não ajuda em nada, pois o custo continua quadrático.
• O algoritmo não é estável.
18
void Selecao (TItem* v, int n) { int i, j, Min; TItem aux; for (i = 0; i < n - 1; i++) { Min = i; for (j = i + 1 ; j < n; j++) if (v[j].Chave < v[Min].Chave) Min = j; aux = v[Min]; v[Min] = v[i]; v[i] = aux; }}
Método Seleção
19
void Selecao (TItem* v, int n) { int i, j, Min; TItem aux; for (i = 0; i < n - 1; i++) { Min = i; for (j = i + 1 ; j < n; j++) if (v[j].Chave < v[Min].Chave) Min = j; if (i != Min) { aux = v[Min]; v[Min] = v[i]; v[i] = aux; } }}
Método Seleção – Melhoria!
20
ORDENAÇÃO POR INSERÇÃO
INSERTSORT
Método Inserção
• Algoritmo utilizado pelo jogador de cartas • As cartas são ordenadas da esquerda para direita uma por
uma.
• O jogador escolhe a segunda carta e verifica se ela deve ficar antes ou na posição que está.
• Depois a terceira carta é classificada, deslocando-a até sua correta posição
• O jogador realiza esse procedimento até ordenar todas as cartas
• Alto custo em remover uma carta de uma posição e colocá-la em outra quando a representação é por arranjos
22
void Insercao (TItem* v, int n) { int i,j; TItem aux; for (i = 1; i < n; i++) { aux = v[i]; j = i - 1; while (j >= 0 && aux.Chave < v[j].Chave) { v[j + 1] = v[j]; j--; } v[j + 1] = aux; }}
Método Inserção
23
void Insercao (TItem* v, int n) { int i,j; for (i = n-2; i >= 0; i--) { v[n] = v[i]; j = i + 1; while (v[n].Chave > v[j].Chave) { v[j - 1] = v[j]; j++; } v[j - 1] = v[n] }}
Método Inserção (com sentinela)
24
Análise de Complexidade
• Comparações – C(n)
• No anel mais interno, na i-ésima iteração, o valor de Ci é:
§ melhor caso : Ci (n) = 1
§ pior caso : Ci (n) = i
§ caso medio : Ci(n) = 1/i (1 + 2 + ... + i) = (i+1)/2
• Assumindo que todas as permutações de n são igualmente prováveis no caso médio, temos:
§ melhor caso : C(n) = (1 + 1 + ... + 1) = n - 1
§ pior caso : C(n) = (1 + 2 + ... + n-1) = n2/2 - n/2
§ caso medio : C(n) = ½ (2 + ... + n ) = n2/4 + n/4 – 1/2
25
Análise de Complexidade
• Movimentações – M(n)
• No anel mais interno, na i-ésima iteração, o valor de Mi é:
§ melhor caso : Mi (n) = 0
§ pior caso : Mi (n) = i
§ caso medio : Mi(n) = 1/i (0 + 1 + 2 + ... + i-1) = (i-1)/2
• Assumindo que todas as permutações de n são igualmente prováveis no caso médio, temos:
§ melhor caso : M(n) = (2 + 2 + ... + 2) = 2n - 2
§ pior caso : M(n) = (2+1 + ... + 2+n-1) = (n2+3n-4)/2
§ caso medio : M(n) = ½ (2 + 3 + ... + n ) = (n2 + n – 2)/2
26
Ordenação por Inserção
• O número mínimo de comparações e movimentos ocorre quando os itens estão originalmente em ordem.
• O número máximo ocorre quando os itens estão originalmente na ordem reversa.
• É o método a ser utilizado quando o arquivo está “quase” ordenado.
• É um bom método quando se deseja adicionar uns poucos itens a um arquivo ordenado, pois o custo é linear.
• O algoritmo de ordenação por inserção é estável.
27
Ordenação por Comparação
• Métodos simples:
• Adequados para pequenas entradas.
• Requerem O(n2) comparações.
• Produzem programas pequenos (pouco código).
28
Ordenação por Comparação
• Métodos eficientes:
• Adequados para entradas maiores.
• Requerem O(n log n) comparações.
• Usam menos comparações.
• As comparações são mais complexas nos detalhes.
• Uma observação importante:
• Métodos simples são mais eficientes para pequenos arquivos.
29
Perguntas?
BUBBLESORT, SELECTSORT E INSERTSORT
EXERCÍCIO
Exercício
• Dada a sequência de números:
3 4 9 2 5 1 8 Ordene em ordem crescente utilizando os três algoritmos aprendidos em sala (BubbleSort, SelectSort e InsertSort), apresentando a sequência dos números a cada passo.
32
