PAA-3-algoritmosOrdenacao

Prévia do material em texto

ALGORITMOS DE 
ORDENAÇÃO 
Profa. Thaís Alves Burity Rocha 
Agenda 
 O que são algoritmos de ordenação 
 Ordenação por seleção (Selection Sort) 
 Ordenação por inserção (Insertion Sort) 
 Bubble Sort 
 Ordenação por intercalação (Merge Sort) 
 Princípio da Divisão e Conquista 
Algoritmos de Ordenação 
 Algoritmos que ordenam uma dada sequência de 
elementos 
 
 Ordenação 
Entrada: Uma sequência de n números <a1, a2, …, an > 
Saída: Uma reordenação da sequência de entrada <a1’, a2’, …, an’ >, 
onde a1’ ≤ a2’ ≤ … ≤ a3’ 
Ordenação por Seleção 
 Um dos algoritmos mais simples de ordenação 
 Algoritmo: 
 Selecione o menor item do vetor 
 Troque-o com o item da primeira posição do vetor 
 Repita essas duas operações com os n - 1 itens 
restantes, depois com os n - 2 itens, até que reste 
apenas um elemento 
Ordenação por Seleção 
 As chaves em negrito sofreram uma troca em si 
Ordenação por Seleção 
Ordenação por Seleção 
 Adequado para conjuntos pequenos de valores 
 
 Mesmo que o conjunto de entrada esteja ordenado, o 
número de operações realizadas é o mesmo 
 
 Algoritmo não é estável 
 Um algoritmo de ordenação é estável se preserva a ordem de 
registros de chaves iguais 
 Entrada: 
 
 Saída de um algoritmo estável: 
 
 Saída de um algoritmo não estável: 
 
C 
1 
B 
2 
B 
3 
A 
4 
A 
4 
B 
2 
B 
3 
C 
1 
A 
4 
B 
3 
B 
2 
C 
1 
Ordenação por Inserção 
 Método preferido dos jogadores de cartas 
 Algoritmo: 
 Em cada passo a partir de i=2 faça: 
 Selecione o i-ésimo item da seqüência fonte 
 Coloque-o no lugar apropriado na seqüência destino de 
acordo com o critério de ordenação 
Ordenação por Inserção 
 As chaves em negrito representam a seqüência destino 
Ordenação por Inserção 
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 conjunto está 
“quase” ordenado 
 É um bom método quando se deseja adicionar uns 
poucos itens a um conjunto ordenado, pois o custo é 
linear 
 Algoritmo é estável 
Bubble Sort 
 Um dos algoritmos mais simples que existem 
 Algoritmo: 
 Percorra o vetor inteiro comparando elementos 
adjacentes (dois a dois) 
 Troque as posições dos elementos se eles estiverem 
fora de ordem 
 Repita os dois passos acima com os primeiros n-1 itens, 
depois com os primeiros n-2 itens, até que reste apenas 
um item 
 
Bubble Sort 
 As chaves em vermelho foram empurradas para o 
fim do vetor a cada passada 
Bubble Sort 
 j percorrer o vetor do 
inicio até i-1 
 i percorre o vetor na 
ordem contrária e 
delimita o sub-vetor 
ordenado (as últimas 
posições do vetor) 
 Logo, j percorre os 
elementos que ainda 
vão ser ordenados 
 
Bubble Sort 
 Método muito simples, mas custo alto 
 Adequado apenas para conjuntos pequenos 
 
 Número de operações não se altera se vetor já 
está (parcialmente) ordenado 
Método da Bolha Melhorado: Termina execução 
quando nenhuma troca é realizada após uma passada 
pelo vetor 
 
 Algoritmo é estável 
Ordenação por Intercalação 
Merge Sort - recursivo 
 Princípio da Divisão e Conquista: 
 Divida o vetor A em dois subconjuntos A1 e A2 
 Solucione os sub-problemas associados a A1 e A2 
 Em outras palavras, ordene cada subconjunto 
separadamente (chamada recursiva) 
 Recursão pára quando atinge sub-problemas de tamanho 1 
 Combine as soluções de A1 e A2 em uma solução para 
A: intercale os dois sub-vetores A1 e A2 e obtenha o 
vetor ordenado 
 Operação chave: intercalação 
Ordenação por Intercalação 
Merge Sort - recursivo 
Ordenação por Intercalação 
Merge Sort - iterativo 
A ideia é muito simples: 
a cada iteração, intercalamos 
dois "blocos“ com b elementos 
cada: o primeiro bloco com o 
segundo, o terceiro com o 
quarto etc. A variável b 
assume os valores 1, 2, 4, . . . . 
 
 
 
A função intercala recebe 
vetores crescentes v[p..q-1] e 
v[q..r-1] e rearranja v[p..r-1] 
em ordem crescente 
Ordenação por Intercalação 
Merge Sort - iterativo 
 Ordem de complexidade linear O(n) 
 
 Precisa de vetor auxiliar 
 
 Para o caso de intercalação de listas lineares, o 
procedimento pode ser realizado com a mesma 
complexidade e sem necessidade de memória auxiliar, 
bastando a manipulação de apontadores 
 
 Algoritmo é estável 
Animação de comparação entre os 
algoritmos de ordenação 
 Animação comparação a eficiência entre os 
algoritmos: Inserção, Seleção, de Bolha (Bubble), 
Shell, Merge (Intercação), Heap e Quick 
 Com as condições iniciais do vetor: sortidos de forma 
randômica, quase ordenado, ordenados de forma 
reversa e com muitos semelhantes. 
 
 http://www.sorting-algorithms.com/ 
 
 
Danças Nerds (AlgoRythmics) 
 Dança do: 
 SelectionSort (Seleção) 
 http://www.youtube.com/watch?v=Ns4TPTC8whw&feature=related 
 InsertionSort (Inserção) 
 http://www.youtube.com/watch?v=ROalU379l3U&feature=related&noredirect=1 
 BubbleSort (Bolha) 
 http://www.youtube.com/watch?v=lyZQPjUT5B4&feature=related 
 Mergesort (Intercalação) 
 http://www.youtube.com/watch?v=XaqR3G_NVoo&feature=related 
 ShellSort 
 http://www.youtube.com/watch?v=CmPA7zE8mx0&context=C4d68aa6ADvjVQa1Ppc
FN9twQZ58yrq9ObECCv7O5WnH5EXzSag3U 
 QuickSort 
 http://www.youtube.com/watch?v=ywWBy6J5gz8&context=C4b980f4ADvjVQa1Ppc
FN9twQZ58yrq7-lXA8nBwwQpF06qM9UGyU 
Referências 
 Projeto de Algoritmos. Nívio Ziviani 
 Análise de Algoritmos. Paulo Feofiloff