Baixe o app para aproveitar ainda mais
Prévia do material em texto
1 Estrutura de Dados e Algoritmos 1 Algoritmos de Ordenação por Comparação - I Prof. Cláudio Campelo, PhD Departamento de Sistemas & Computação / UFCG Contexto 2 2 The Maggie Sort 3 http://www.youtube.com/watch?v=Zybl598sK24 Ordenação 4 � Uma das tarefas mais fundamentais e extensivamente usadas na computação: � Bancos de dados, compiladores, interpretadores, sistemas operacionais, etc. � Ordenação é o processo de arranjar um conjunto de informações semelhantes em ordem crescente ou decrescente � Diversos algoritmos � Ordenação por comparação � Ordenação em tempo linear 3 Algoritmo In-place 5 � A ordenação é feita no mesmo local onde os dados são armazenados. � No máximo precisa de memória extra de tamanho constante Algoritmo Estável 6 � Um algoritmo de ordenação é estável se dados dois elementos R e S com a mesma chave, se R aparece antes de S na lista original, R aparecerá antes de S na lista ordenada final � Exemplo: 10(Carlos) 2(Débora) 7(João) 7(José) 2(Débora) 7(João) 7(José) 10(Carlos) 4 Bubble Sort 7 Bubble Sort 8 � O bubble sort, ou ordenação por flutuação (literalmente "por bolha"), é um algoritmo de ordenação dos mais simples. A idéia é percorrer o vetor diversas vezes, a cada passagem fazendo flutuar para o topo o maior elemento da sequência. � As trocas acontecem com o elemento subsequente � Exemplo: [8,4,7,1] [4,8,7,1] [4,7,8,1] [4,7,1,8] [4,7,1,8] [4,7,1,8] [4,1,7,8] [4,1,7,8] [1,4,7,8] [1,4,7,8] Animação 5 Bubble Sort 9 � Exercício: � Ordene a lista a seguir utilizando o bubble sort � 21, 23, 2, 34, 245, 33, 66 Bubble Sort 10 � Como seria o algoritmo do Bubble Sort? SWAP(A, int i, int j) { int temp = A[i]; A[i] = A[j]; A[j] = temp; } BUBBLE-SORT( A) { n = length(A) for i ← 1 to n – 1 { for j ← 1 to n – i { if (A[j] > A[j+1]) { swap(A, j, j+1) } } } } 6 Bubble Sort 11 � Qual o tempo do Bubble Sort no pior caso? BUBBLE-SORT( A) { n = length(A) for i ← 1 to n – 1 { for j ← 1 to n – i { if (A[j] > A[j+1]) { swap(A, j, j+1) } } } } )( 22 )1()( 2 21 1 n nnnninT n i Θ=−=−==∑ − = n – 1 iterações n – 2 iterações n – 3 iterações … 1 iteração Bubble Sort 12 � Qual o tempo do Bubble Sort no pior caso? n – 1 iterações n – 2 iterações n – 3 iterações … 1 iteração BUBBLE-SORT( A) { n = length(A) for i ← 1 to n – 1 { for j ← 1 to n – i { if (A[j] > A[j+1]) { swap(A, j, j+1) } } } } )( 22 )1()( 2 21 1 n nnnninT n i Θ=−=−==∑ − = O que acontece no melhor caso? 7 Bubble Sort 13 � O que esse algoritmo faz? XXXXXX(A) { n = length(A) for i← 1 to n-1 { for j← n-1 to i { if ( A[j-1] > A[j] ) { swap(A, j-1, j) } } } } Bubble Sort 14 � O que esse algoritmo faz? YYYYYYYY(A) { swapped = true; n = length(A) while swapped { swapped = false; for i← 1 to n-2 { if (A[i] > A[i+1]) { swap(A, i, i+1) swapped = true } } } } 8 Características 15 � Fácil de implementar � Fácil de entender � In place: não precisa de espaço extra � Stable: preserva a ordem � Pode ser útil para valores de n pequenos � Número alto � comparações � Swap (trocas) O(n2) � Muito ruim na prática “Bubble sort seems to have nothing to recommend it.” [Donald Knuth] Selection Sort 16 9 Selection Sort 17 � Lógica do selection sort: � Encontre o menor elemento da lista � Troque com o primeiro elemento da lista � Faça o processo novamente para o restante da lista, começando da próxima posição � Exemplo: [8,4,7,1] [1,4,7,8] [1,4,7,8] [1,4,7,8] [1,4,7,8] [1,4,7,8] Animação Selection Sort 18 � Exercício: � Ordene a lista a seguir utilizando o selection sort � 21, 23, 2, 34, 245, 33, 66 10 Selection Sort 19 � Como seria o algoritmo do Selection Sort? SELECTION-SORT(A) { n = length(A) for i ← 1 to n-1 { min ← i for j ← (i + 1) to n { if A[j] < A[min] { min ← j } } swap (A, i, min) } } Selection Sort 20 � Qual o tempo do Selection Sort no pior caso? SELECTION-SORT(A) { n = length(A) for i ← 1 to n-1 { min ← i for j ← (i + 1) to n { if A[j] < A[min] { min ← j } } swap (A, i, min) } } 11 Selection Sort 21 � Qual o tempo do Selection Sort no pior caso? SELECTION-SORT(A) { n = length(A) for i ← 1 to n-1 { min ← i for j ← (i + 1) to n { if A[j] < A[min] { min ← j } } swap (A, i, min) } } O que acontece no melhor caso? 2..n (n – 1) iterações 3..n (n – 2) iterações 4..n (n – 3) iterações … … n..n 1 iteração )( 22 )1()( 2 21 1 n nnnninT n i Θ=−=−==∑ − = Selection Sort 22 � O que esse algoritmo faz? XXXXXX-SORT(A) { n = length(A) for i ← n downto 2 { m ← i for j ← 1 to i { if A[j] > A[m] { m ← j } } swap (A, i, m) } } 12 Características 23 � Fácil de implementar � Fácil de entender � In place: não precisa de espaço extra � Stable � Depende de como é feito o swap � Pode ser útil para valores de n pequenos � Melhor que o bubble sort (tem menos trocas) mas perde para o insertion sort � Menos swap (trocas) Insertion Sort 24 13 Insertion Sort 25 � Lógica do insertion sort: similar à ordenação de cartas um baralho com a seguinte idéia: � Coloque todas as cartas que deseja ordenar na mão direita; � Pegue uma carta com a mão direita e coloque na mão esquerda; � Faça isso para as demais cartas colocando-as de forma ordenada na mão esquerda. Insertion Sort 26 5 5 1 1 7 7 9 9 6 6 Como ordenar as cartas acima? 14 Insertion Sort 27 5 5 1 1 9 9 7 7 6 6 1 1 5 5 9 9 7 7 6 6 Insertion Sort 28 15 1 1 5 5 9 9 7 7 6 6 Insertion Sort 29 1 1 5 5 7 7 9 9 6 6 Insertion Sort 30 16 1 1 5 5 7 7 9 9 6 6 Insertion Sort 31 Animação Insertion Sort 32 � Exercício: � Ordene a lista a seguir utilizando o insertion sort � 21, 23, 2, 34, 245, 33, 66 17 Insertion Sort 33 � Como seria o algoritmo do Insertion Sort? INSERTION-SORT(A) { n = length(A) for j ←2 to n { key ←A[ j] i ←j –1 while i > 0 and A[i] > key { A[i+1] ← A[i] i ←i –1 } A[i+1] = key } } Insertion Sort 34 � Como seria o algoritmo do Insertion Sort? INSERTION-SORT(A) { n = length(A) for j ←2 to n { key ←A[ j] i ←j –1 while i > 0 and A[i] > key { A[i+1] ← A[i] i ←i –1 } A[i+1] = key } } 1..1 1 iteração 2..1 2 iterações 3..1 3 iterações … … (n-1)..1 (n – 1) iterações )( 22 )1()( 2 21 1 n nnnninT n i Θ=−=−==∑ − = 18 Insertion Sort 35 � O que esse algoritmo faz? XXXXXXXX(A) { n = length(A); endOfOrderedList = 1; while(endOfOrderedList < n){ int next = A[endOfOrderedList + 1]; for j ← endOfOrderedList downto 1 { if (next < A[j]) { swap(A, j, j+1); } } endOfOrderedList++; } } Características 36 � Fácil de implementar � Fácil de entender � In place: não precisa de espaço extra � Stable � Muita escrita (troca) e menos comparações � Melhor Caso � O(n) � Caso Médio � O(n2/4) � Eficiente para valores de n pequenos � Melhor do que bubble e selection sort 19 Outros Algoritmos de Ordenação por Comparação 37 Gnome Sort 38 � Inventor: Hamid Sarbazi-Azad (2000) � Idéia: � Adota um pivot (que tenha anterior); � Normalmenteo 2° elemento; � Olha para o anterior; � Se o pivot e o anterior estão na ordem correta então incrementa o pivot. � Se eles não estão na ordem correta então troca eles e decrementa o pivot; � Condições: se não existe anterior ao pivot então anda para frente (ao invés de decrementar). Se não tem próximo, então termina. 20 Gnome Sort 39 � Como seria o algoritmo? Array Atual Ação [5,3,2,4] A[pos] < A[pos-1], swap. pos <= 2, incrementa pos [3,5,2,4] A[pos] < A[pos-1], swap pos > 2, decrementa pos [3,2,5,4] A[pos] < A[pos-1], swap pos <= 2, incrementa pos [2,3,5,4] A[pos] >= A[pos-1], incrementa pos. [2,3,5,4] A[pos] < A[pos-1], swap pos > 2, decrementa pos [2,3,4,5] A[pos] >= A[pos-1], incrementa pos. [2,3,4,5] A[pos] >= A[pos-1], incrementa pos. [2,3,4,5] pos > length(A), fim ! Gnome Sort 40 � Como seria o algoritmo? � Animação 21 Gnome Sort 41 � Como seria o algoritmo? GNOME-SORT(A) { pos := 2 //começando com 1 while pos <= length(A) { //enquanto não atinge o último elemento if (A[pos] >= A[pos-1]) { //se está na ordem correta pos := pos + 1 } else { swap (A, pos, pos-1) if (pos > 2) { //se maior que 2, decrementa pos := pos - 1 } else { //se menor ou igual a 2, incrementa pos := pos + 1 } } } } Gnome Sort 42 � Análise � Pior caso = O(n2) � Melhor caso = O(n) � Caso médio = O(n2) 22 Comb Sort 43 � Variação do bubble sort � Inventor Wlodzimierz Dobosiewicz (1980) � Focado em melhorar a entrada do bubble sort antes de aplicá-lo (bubble compara elementos de distância 1) � Idéia: � A distância começa por gap = tamanho/fator (fator=1.25) � A entrada é ordenada com as trocas considerando elementos distanciados por gap � gap é atualizado (gap = gap/fator) até 1 � Quando gap=1 combo sort continua até o array estar todo ordenado � Animação Comb Sort 44 � Como seria o algoritmo? 23 Comb Sort 45 � Como seria o algoritmo? COMB-SORT(A) gap := length(A) //initialize gap size while (gap > 1 and swaps) { gap := gap / 1.25 if (gap<1) gap := 1 i := 1 swaps := false while (i + gap <= length(A) ) { if ( A[i] > A[i+gap] ) { //faz trocas considerando distancia = gap swap(A, i, i+gap) swaps := true // ocorreu troca } i := i + 1 } } } Comb Sort 46 � Análise � Pior caso = O(n2) � Melhor caso = O(n) 24 Questões de Implementação 47 � Como desenvolver/adaptar os algoritmos de ordenação vistos para ordenar tipos genéricos? � Ao invés de trabalhar com inteiros precisamos trabalhar com um tipo T. Questões de Implementação 48 SWAP(A, int i, int j) {{ // A é uma lista de itens comparáveis int temp = A[i]; A[i] = A[j]; A[j] = temp; } BUBBLE-SORT( A) { // A é uma lista de itens comparáveis n = length(A) for i ← 1 to n – 1 { for j ← 1 to n – i { if (A[j] > A[j+1]) { swap(A[j]), A[j+1]) } } } } 25 Questões de Implementação 49 SWAP(A, int i, int j) {{ // A é uma lista de itens Comparable int temp = A[i]; A[i] = A[j]; A[j] = temp; } BUBBLE-SORT( A) { // A é uma lista de itens Comparable n = length(A) for i ← 1 to n – 1 { for j ← 1 to n – i { if (A[j] > A[j+1]) { swap(A[j]), A[j+1]) } } } } Questões de Implementação 50 SWAP(A, int i, int j) {{ // A é uma lista de itens Comparable int temp = A[i]; A[i] = A[j]; A[j] = temp; } BUBBLE-SORT( A) { // A é uma lista de itens Comparable n = length(A) for i ← 1 to n – 1 { for j ← 1 to n – i { if (A[j].compareTo(A[j+1]) > 0) { swap(A[j]), A[j+1]) } } } } 26 Questões de Implementação 51 � Exemplo: bubblesort � Como implementar o bubblesort considerando apenas um “pedaço” do vetor a ser ordenado? bubbleSort( A, int leftIndex, int rightIndex ) { n = length(A) for i ← 1 to n – 1 { for j ← 1 to n-i { if (A[j].compareTo(A[j+1]) > 0){ swap(A,j,j+1) } } } } Questões de Implementação 52 � Exemplo: bubblesort � Como implementar o bubblesort considerando apenas um “pedaço” do vetor a ser ordenado? bubbleSort( A, int leftIndex, int rightIndex ) { n = length(A) for i ← 1 to n – 1 { for j ← 1 to n-i { if (A[j].compareTo(A[j+1]) > 0){ swap(A,j,j+1) } } } } Adaptar para os novos limites!
Compartilhar