Ordenação de Dados em Algoritmos

Prévia do material em texto

Roteiro da Aula 15 
 
Agenda 
 
• Ordenação, ordenação e mais ordenação. 
 
 
 
Ordenação 
A necessidade de por os dados em ordem é muito comum 
• Visualização, impressão 
• Torna mais rápida a busca, encontrar o mínimo ou o máximo, calcular mediana e moda, etc. 
 
 
 
Selection sort 
• Selecione o menor e mova para a frente 
• Pesquisa para encontrar o mínimo 
• Coloque na primeira posição 
• Poderia mover os demais elementos para fazer espaço, mas é mais rápido apenas trocá-lo com o 
elemento que atualmente ocupa a primeira posição 
• Repita o procedimento para o segundo menor, terceiro menor e assim por diante. 
 
 
 
Selection sort: código 
def selectionSort(v): 
 for i in range(len(v)): 
 for j in range(i + 1, len(v)): 
 if v[j] < v[i]: 
 # traz o menor encontrado para a posição i 
 v[i], v[j] = v[j], v[i] 
 
 
links: 
http://www.youtube.com/watch?v=Ns4TPTC8whw 
no arquivo Animacoes.rar: 
Select-sort with Gypsy folk dance(360p_H.264-AAC).mp4 
selectionSort.swf 
selectionSortAlgorithmDemo.swf 
 
 
 
Uma versão mais eficiente do algoritmo 
def selectionSort(v): 
 for i in range(len(v) - 1): 
 indiceMenor = i 
 # acha o indice do menor elemento de i até o final 
 for j in range(i+1, len(v)): 
 if v[j] < v[indiceMenor]: 
 indiceMenor = j 
 # traz o menor encontrado para o início 
 v[i], v[indiceMenor] = v[indiceMenor], v[i] 
 
 
 
Selection sort: análise 
Contagem do trabalho efetuado dentro dos laços 
• A primeira iteração faz N-1 comparações, a segunda N-2, e assim por diante. 
• Uma troca de posições por iteração 
 
 
123321 ++++−+−+− ΚNNN 
“Soma Gaussiana” 
 
 
Adicione a soma a ela própria: 
( ) NN
NNNNNN
NNN
NNN
⋅−=
++++++=
−+−+−++++
++++−+−+−
1
...
123...321
123...321
 
 
 
( ) ( )2
2
1
N
NN
Soma ∫ Ο=
−
= 
 
 
 
Insertion Sort 
Como você poderia ordenar uma mão de cartas em um jogo com baralhos... 
• Cada elemento subseqüente inserido no lugar correto 
• Comece com o primeiro elemento (já ordenado) 
• Insere o elemento seguinte na posição correta em relação ao primeiro 
• Repetir o procedimento para o terceiro, quarto, etc. 
• Move os elementos durante a inserção para fazer espaço 
 
 
 
Insertion Sort: código 
def insertionSort(v): 
 for i in range(1, len(v)): 
 for j in range(i - 1, -1, -1): 
 if v[j + 1] > v[j]: break 
 v[j + 1], v[j] = v[j], v[j + 1] 
 
 
link: 
http://www.youtube.com/watch?v=ROalU379l3U&feature=related 
no arquivo Animacoes.rar: 
Insert-sort with Romanian folk dance(480p_H.264-AAC).flv 
insertionSort.swf 
insertionSortAlgorithmDemo.swf 
 
 
 
Insertion Sort: uma versão um pouco mais otimizada 
def insertionSort(v): 
 for i in range(1, len(v)): 
 cur = v[i] # o elemento a ser inserido 
 j = i - 1 
 while j >= 0 and v[j] > cur: 
 v[j+1] = v[j] 
 j -= 1 
 v[j+1] = cur 
 
 
 
Insertion sort: análise 
Contagem do trabalho efetuado dentro dos laços 
• Na primeira iteração, o laço interno faz 1 comparação e, no máximo, um deslocamento. 
• A segunda iteração faz no máximo duas comparações/deslocamentos, a terceira, no máximo três 
comparações/deslocamentos e assim por diante. 
• A última iteração, potencialmente, faz N-1 comparações/deslocamentos. 
 
 
Como a entrada afeta o desempenho do algoritmo? 
• Qual é o melhor caso1? E o pior2? 
• Qual é a média esperada? 
 
 
 
Insertion vs Selection 
Complexidade? 
 
Mix de operações? 
• Número de deslocamentos vs comparações 
 
Quais são as melhores/piores entradas? 
 
1
 O conjunto de dados totalmente ordenado 
2
 O conjunto de dados em ordem reversa 
 
Facilidade de codificação? 
 
Por que precisamos de vários algoritmos? 
 
 
no arquivo Animacoes.rar: 
insertion_vs_selection.swf 
 
 
 
Crescimento quadrático 
Tempos medidos 
10000 3s 
20000 13s 
50000 77s 
100000 5min 
 
 
A cada vez que a entrada dobra de tamanho, o tempo de processamento é multiplicado por quatro. 
• Viável para pequenos conjuntos de entrada, mas rapidamente torna-se incontrolável. 
 
 
Mas se a entrada é reduzida à metade, o tempo de processamento é dividido por quatro! 
• Hmmm ...Será que a recursão pode salvar o dia? 
• Se eu tiver duas metades ordenadas, como posso obter o conjunto inteiro ordenado? 
 
 
 
Merge Sort 
Estratégia do tipo “Dividir para conquistar” 
• Divida a entrada no meio 
• Recursivamente, ordene cada metade. 
• Junte as duas metades 
 
 
Estratégia: “Separar é fácil, juntar é difícil” 
• Sem decisões complexas sobre quem vai pra onde, apenas divida no meio. 
• A etapa de mesclagem preserva a ordenação de cada metade 
 
 
 
Merge Sort: código 
def merge(v, left, right): 
 l = 0 
 r = 0 
 for i in range(len(v)): 
 if r == len(right): 
 v[i] = left[l] 
 l += 1 
 elif l == len(left): 
 v[i] = right[r] 
 r += 1 
 elif left[l] <= right[r]: 
 v[i] = left[l] 
 l += 1 
 else: 
 v[i] = right[r] 
 r += 1 
 
 
def mergeSort(v): 
 if len(v) > 1: 
 n1 = len(v)/2 
 left = v[:n1] 
 right = v[n1:] 
 mergeSort(left) 
 mergeSort(right) 
 merge(v, left, right) 
 





+=
2
2)(
N
TNNT 
 
 
Links: 
http://haegar.fh-swf.de/AlgoDat/Sortieren/sorts/MergeSort/mergesort.html 
http://www.youtube.com/watch?v=XaqR3G_NVoo&feature=related 
http://xoax.net/comp/sci/algorithms/Lesson3.php 
no arquivo Animacoes.rar: 
mergeSort.swf 
 
 
 
Uma implementação alternativa 
def merge(v, left, right): 
 for i in range(len(v)): 
 if len(right) == 0 or (len(left) != 0 and left[0] < right[0]): 
 v[i] = left.pop(0) 
 else: 
 v[i] = right.pop(0) 
 
 
def mergeSort(v): 
 if len(v) > 1: 
 n1 = len(v)/2 
 left = v[:n1] 
 right = v[n1:] 
 mergeSort(left) 
 mergeSort(right) 
 merge(v, left, right) 
 
O(1) 
O(N) 
O(N) 
 
 
Merge Sort: análise 
 
 
 
 
Merge Sort: análise 
 
 
( )NNOnívelporNníveisN log*log = 
 
 
no arquivo Animacoes.rar: 
Insertion_vs_Selection_vs_Merge.swf 
 
 
 
Tempo quadrático vs N log N 
Comparação do Selection Sort com o Merge Sort 
MS(N) 
MS(N/2) MS(N/2) 
MS(N/4) 
N/8 N/8 N/8 N/8 N/8 N/8 N/8 N/8 
MS(N/4) MS(N/4) MS(N/4) 
... 
= N 
= N/2 + N/2 
= 4*N/4 
= 8*N/8 
Cada nível 
contribui com N 
MS(N) 
MS(N/2) MS(N/2) 
MS(N/4) 
N/8 N/8 N/8 N/8 N/8 N/8 N/8 N/8 
MS(N/4) MS(N/4) MS(N/4) 
... 
N/2k
 
K níveis 
N/2
k
 = 1 
N = 2
k 
log N = k 
10000 3s 0.05s 
20000 13s 0.15s 
50000 78s 0.38s 
100000 5min 0.81s 
200000 20min 1.7s 
1000000 8hrs (est) 9s 
 
 
( )NNO log parece ser muito bom! Podemos fazer melhor? 
• Os resultados teóricos dizem que não é possível fazer melhor do que ( )NNO log 
• Mas na prática é possível conseguir um ( )NNO log melhor. ☺ 
 
 
 
Quick Sort 
Estratégia do tipo “Dividir para conquistar” 
• Divida a entrada na metade alta e na metade baixa 
• Recursivamente, ordene cada metade. 
• Junte as duas metades 
 
 
“Difícil separar, fácil juntar” 
• Cada elemento é examinado e colocadona metade correta 
• A etapa de mesclagem é trivial