slides algoritmos de ordenacao

Prévia do material em texto

Estruturas de Dados
Algoritmos de Ordenação
Prof. Eduardo Alchieri
 
Algoritmos de Ordenação
(introdução)
 Considere uma sequência arbitrária S = {s1, s2, s3,...sn} 
composta por n ≥ 0 elementos retirados do conjunto universo U
 O objetivo da ordenação é arrumar os elementos de S para 
produzir uma nova sequência S' na qual os elementos de S 
estão em ordem
 O que significa os elementos estarem em ordem?
 Para qualquer dois elementos i, j extraídos de U
 i < j; i = j; i > j
 A relação < é transitiva
 Ordenar os elementos de S é definir uma permutação 
dos elementos de S para produzir S' de acordo com o 
operador “<”
 Em outras palavras, ordenar é o processo de 
organizar um conjunto de elementos em uma ordem
 
Algoritmos de Ordenação
(introdução)
 Exemplos:
 lista telefônica, com os nomes das pessoas em ordem 
alfabética
 bancos, com os atendimentos por ordem de chegada
 hospitais, com os atendimentos em ordem de prioridade
 times, com os jogadores em ordem de técnica
 etc.
 
Algoritmos de Ordenação
(introdução)
 A ordenação visa facilitar a recuperação de um item do 
conjunto
 Busca binária: sabendo que o objeto está em um intervalo e 
com uma função de teste que diz se o objeto está antes, em 
ou depois de uma determinada posição, a busca binária 
divide a quantidade de números que precisam ser vericados 
pela metade a cada iteração
 O(log n)
 
Algoritmos de Ordenação
(introdução)
 Algoritmos de ordenação trabalham sobre a chave de 
ordenação de um registro (claro, podem existir outros dados no 
registro)
 Nome
 Matrícula
 Id
 Código
 Etc
 Chave de ordenação é qualquer tipo de chave sobre a qual 
exista uma regra de ordenação bem definida
 
Algoritmos de Ordenação
(introdução)
 Os métodos de ordenação podem ser de dois tipos:
 Estáveis: as chaves duplicadas mantém suas posições 
relativas na sequência ordenada
 Instáveis: as chaves duplicadas não mantém suas posições 
relativas na sequência ordenada
 Alguns métodos de ordenação mais eficientes são instáveis, 
mas estabilidade pode ser forçada
 
Algoritmos de Ordenação
(métodos de ordenação)
 Método Ineficiente
 Bogosort: O (∞)
 Métodos elementares:
 Inserção: O(n2)
 Bubblesort: O(n2)
 Seleção: O(n2)
 Métodos Eficientes
 Quicksort: O(n log n) (no pior caso é O(n2))
 Heapsort: O(n log n)
 Mergesort: O(n log n)
 Counting Sort: O(n)
 
Algoritmos de Ordenação
(métodos de ordenação)
 Uma outra classificação:
 Ordenação por inserção
 Inserção
 Ordenação por troca
 Bubblesort
 Quicksort
 Ordenação por seleção
 Seleção
 Heapsort
 Ordenação por fusão
 Mergesort
 Ordenação por distribuição
 Counting Sort
 
Algoritmos de Ordenação
(Bogosort)
 Algoritmo é probabilístico
 Pode nunca terminar
 
Algoritmos de Ordenação
(inserção)
 A ideia é separar a lista em duas: a primeira ordenada e a 
segunda aleatoria
1. Para o segundo item em diante, selecione o i-esimo item.
2.Coloque-o no na parte ordenada, na posição correta.
 
Algoritmos de Ordenação
(inserção)
 Algoritmo
Exemplo de funcionamento
 
Algoritmos de Ordenação
(inserção)
 O número mínimo de comparações e movimentos ocorre 
quando os itens estão originalmente em ordem
 Melhor caso: O(n)
 O número máximo ocorre quando os itens estão originalmente 
na ordem reversa
 Pior caso: O(n2)
 Deve ser utilizado quando a lista esta ”quase" ordenada
 Caso medio : O(n2) (com função de custo menor que o pior 
caso)
 E um bom método quando se deseja adicionar uns poucos 
itens a uma lista ordenada, pois o custo e linear
 O algoritmo de ordenação por inserção é estável
 
Algoritmos de Ordenação
(bubblesort)
 A ideia principal do algoritmo é percorrer a lista n − 1 vezes, a 
cada passagem fazendo flutuar para o final o maior elemento 
da sequência (pode ser o contrário).
 O bubblesort é estável
 Algoritmo
bubble(int[] v, int n){
 for(int i = n; i > 1; --i){
 for(int j = 0; j < i – 1; ++j){
 if(v[ j ] > v [ j + 1]){
 troca(j, j + 1) 
 }
 } 
 }
}
 
Algoritmos de Ordenação
(bubblesort)
 Exemplo
3 1 4 1 5 9 2 6 5 4
i=10 1 3 1 4 5 2 6 5 4 9
i=9 1 1 3 4 2 5 5 4 6 9
i=8 1 1 3 2 4 5 4 5 6 9
i=7 1 1 2 3 4 4 5 5 6 9
i=6 1 1 2 3 4 4 5 5 6 9
i=5 1 1 2 3 4 4 5 5 6 9
i=4 1 1 2 3 4 4 5 5 6 9
i=3 1 1 2 3 4 4 5 5 6 9
i=2 1 1 2 3 4 4 5 5 6 9
 
Algoritmos de Ordenação
(bubblesort)
 Otimização (código em java)
public static void bubbleSort (int [] vetor){
 boolean houveTroca = true;
 while (houveTroca) {
 houveTroca = false;
 for (int i = 0; i < (vetor.length)-1; i++){
 if (vetor[i] > vetor[i+1]){
 int variavelAuxiliar = vetor[i+1];
 vetor[i+1] = vetor[i];
 vetor[i] = variavelAuxiliar;
 houveTroca = true;
 }
 }
 } 
}
 
Algoritmos de Ordenação
(seleção)
 A ideia é encontrar o menor elemento do vetor e posicioná-lo 
corretamente
 Algoritmo
 
Algoritmos de Ordenação
(seleção)
 Exemplo
Animação
 
Algoritmos de Ordenação
(seleção)

 
Algoritmos de Ordenação
(quicksort)
 Proposto por Charles Hoare em 1960.
 É o algoritmo de ordenação mais rápido que se conhece para 
uma ampla variedade de situações
 Provavelmente é o mais utilizado
 Não é estável
 A ideia básica é dividir o problema de ordenar um conjunto com 
n itens em dois problemas menores (dividir para conquistar)
 Os problemas menores são ordenados independentemente
 Os resultados são combinados para produzir a solução final
 
Algoritmos de Ordenação
(quicksort)
 Passos do algoritmo
1. Escolher o elemento pivô 
● Ponto fundamental do algoritmo
2. Reordenar a lista de acordo com o pivô
● Neste ponto, o pivô estará na sua posição final (ordenado)
3. Reaodenar recursivamente as sub-listas com elementos 
menores/maiores que o pivô
 
Algoritmos de Ordenação
(quicksort)
 
Algoritmos de Ordenação
(quicksort)
 A escolha do pivô é um ponto fundamental do algoritmo
 Pior caso: o pivô escolhido é sempre um extremo do arquivo
 Caso médio: ocorre quando cada partição divide o arquivo 
em duas partes iguais
 Várias formas de escolher o pivô:
 Pegar o primeiro elemento
 Pegar o último elemento
 Média entre o primeiro e último elemento
 Média entre três elementos
 
Algoritmos de Ordenação
(heapsort)
 Possui o mesmo princípio de funcionamento da ordenação por 
seleção e também não é estável
 Utiliza uma estrutura de dados chamada heap para ordenar os 
elementos a medida que os insere na estrutura
 Ao final das inserções, os elementos podem ser sucessivamente 
removidos da raiz da heap, na ordem desejada
 A heap pode ser representada como uma árvore ou como um 
vetor
 O custo para inserir ou remover um elemento da heap é O(log n)
 
Algoritmos de Ordenação
(heapsort)
 
Algoritmos de Ordenação
(mergesort)
 Usa a estratégia de dividir para conquistar
 É mais rápido ordenar vetores menores que maiores
 É mais rápido unir dois vetores ordenados do que dois não 
ordenados
 Passos do algoritmo
1.Se o tamanho da lista for 0 ou 1, já está ordenada
2.Dividir a lista em duas partes (de mesmo tamanho)
3.Ordenar cada sub-lista recursivamente
4.Combinar as sub-listas (em ordem)
 
Algoritmos de Ordenação
(mergesort)
 
Algoritmos de Ordenação
(mergesort)Algoritmos de Ordenação
(counting sort)
 Assume-se que as chaves que serão ordenadas estão 
uniformemente distribuídas em um intervalo conhecido(por 
exemplo, de 1 a m).
 É um algoritmo estável.
 Passos do algoritmo
 Inicialize um vetor de contadores, inicialmente em zero
 Percorra o vetor original, incrementando os contadores dos 
elementos encontrados
 Coloque os elementos no vetor original, de acordo com os 
contadores
 
Algoritmos de Ordenação
(counting sort)
 Algoritmo
bucketsort(int[] v){
 for(int i = 0; i < m; ++i){ //m é o número de contadores
 contador[i] = 0;
 }
 for(int j = 0; j < n; ++i){ //n é o tamanho de v
 contador[v[j]]++;
 }
 j = 0;
 for(int i = 0; i < m; ++i){
 while(contador[i] > 0){
 contador[i]--; v[j++] = i;
 }
 }
}
 
Algoritmos de Ordenação
(bucketsort)
 O tempo total de processamento é O(m+n)
 Se n = m, então o custo fica O(n)
 Porém, consome mais memória
 É necessário um espaço de O(m) para o vetor de 
contadores
 
Algoritmos de Ordenação
(demonstrações)
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31