Embed Size (px)
Citation preview
Algoritmos de Ordenação
Profa. Sheila Morais de Almeida
DAINF-UTFPR-PG
junho - 2018
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 1 / 87
Este material é preparado usando como referências os textos dos seguintes
livros.
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 2 / 87
Análise de Algoritmos
Vamos analisar o Algoritmo Ordenação por Inserção.
Quantas operações de comparação são executadas?
Algoritmo Ordenação por Inserção
Entrada: vetor v [1..n] de inteiros; n número de elementos no vetor
Para i de 2 a n faça:
j ← i − 1
Enquanto j > 0 && v [i ] < v [j ] faça:j ← j − 1
t ← v [i ]Para k de i − 1 a j + 1 faça:
v [k + 1]← v [k]v [j + 1]← t
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 3 / 87
Análise de Algoritmos
Para o Algoritmo de Ordenação por Inserção, apresente uma instância
• de melhor caso;
• de pior caso;
• e de caso médio.
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 4 / 87
Análise de Algoritmos
Algoritmo Ordenação por Inserção
Entrada: vetor v [1..n] de inteiros; n número de elementos no vetor
Para i de 2 a n faça:
j ← i − 1
Enquanto j > 0 && v [i ] < v [j ] faça:j ← j − 1
t ← v [i ]Para k de i − 1 a j + 1 faça:
v [k + 1]← v [k]v [j + 1]← t
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 5 / 87
Análise de Algoritmos
Para o Algoritmo de Ordenação por Inserção, apresente uma instância
• de melhor caso: vetor em ordem crescente.
• de pior caso: vetor em ordem decrescente.
• e de caso médio: quando v [i ] é considerado, cada número de v [0] av [i − 1] tem 50% de chance de ser maior que v [i ] e 50% de chance de
ser menor que v [i ]. Para um exemplo, podemos supor:
• os números em posições de 0 a b i2c são menores que v [i ] e
• os números em posições de b i2c+ 1 a i − 1 são maiores que v [i ].
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 6 / 87
Análise de Algoritmos
Para o Algoritmo de Ordenação por Inserção, apresente uma instância
• de melhor caso: vetor em ordem crescente.
• de pior caso: vetor em ordem decrescente.
• e de caso médio: quando v [i ] é considerado, cada número de v [0] av [i − 1] tem 50% de chance de ser maior que v [i ] e 50% de chance de
ser menor que v [i ]. Para um exemplo, podemos supor:
• os números em posições de 0 a b i2c são menores que v [i ] e
• os números em posições de b i2c+ 1 a i − 1 são maiores que v [i ].
Ex.: 90 12 18 83 24 71 67 35 58 40.
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 7 / 87
Análise de complexidade de tempo no pior caso
Considere o Algoritmo de Ordenação por Inserção:
Algoritmo Ordenação por Inserção
Entrada: vetor v [1..n] de inteiros; n número de elementos no vetor
Para i de 2 a n faça:
j ← i − 1
Enquanto j > 0 && v [i ] < v [j ] faça:j ← j − 1
t ← v [i ]Para k de i − 1 a j + 1 faça:
v [k + 1]← v [k]v [j + 1]← t
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 8 / 87
Análise de complexidade de tempo no pior caso
Pergunta: Quantas instruções básicas do modelo computacional RAM
(operações aritméticas básicas, atribuições e comparações) são executadas
pelo Algoritmo de Ordenação por Inserção, considerando uma entrada de
tamanho n de pior caso?
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 9 / 87
Análise de complexidade de tempo no pior caso
Considere o Algoritmo de Ordenação por Inserção:
Algoritmo Ordenação por Inserção
Entrada: vetor v [1..n] de inteiros; n número de elementos no vetor
Para i de 2 a n faça: 2+ 3(n − 1) = 3n − 1
j ← i − 1 2(n − 1) = 2n − 2
Enquanto j > 0 && v [i ] < v [j ] faça: 2∑n−1
c=1 c + (n − 1)∗
j ← j − 1 2∑n−1
c=1 c = n2 − nt ← v [i ] n − 1
Para k de i − 1 a j + 1 faça: 4n(n−1)2
+ 4(n − 1)†
v [k + 1]← v [k] n(n − 1) = n2 − nv [j + 1]← t 2(n − 1) = 2n − 2
∗2∑n−1
c=1 c + (n − 1) = n(n − 1) + (n − 1) = (n + 1)(n − 1) = n2 − 1
†4n(n−1)
2+ 4(n − 1) = 2n2 + 2n − 4
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 10 / 87
Análise de complexidade de tempo no pior caso
Considere o Algoritmo de Ordenação por Inserção:
Algoritmo Ordenação por Inserção
Entrada: vetor v [1..n] de inteiros; n número de elementos no vetor
Para i de 2 a n faça: 2+ 3(n − 1) = 3n − 1
j ← i − 1 2(n − 1) = 2n − 2
Enquanto j > 0 && v [i ] < v [j ] faça: n2 − 1
j ← j − 1 2∑n−1
c=1 c = n2 − nt ← v [i ] n − 1
Para k de i − 1 a j + 1 faça: 2n2 + 2n − 4
v [k + 1]← v [k] n(n − 1) = n2 − nv [j + 1]← t 2(n − 1) = 2n − 2
Total: 5n2 + 8n − 11
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 11 / 87
Análise de Algoritmos de Ordenação
Bubble Sort
262211 0704 30
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 12 / 87
Análise de Algoritmos de Ordenação
Bubble Sort
262211 0704 30
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 13 / 87
Análise de Algoritmos de Ordenação
Bubble Sort
262211 0704 30
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 14 / 87
Análise de Algoritmos de Ordenação
Bubble Sort
262211 0704 30
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 15 / 87
Análise de Algoritmos de Ordenação
Bubble Sort
262211 0704 30
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 16 / 87
Análise de Algoritmos de Ordenação
Bubble Sort
262211 0704 30
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 17 / 87
Análise de Algoritmos de Ordenação
Bubble Sort
262211 0704 30
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 18 / 87
Análise de Algoritmos de Ordenação
Bubble Sort
262211 0704 30
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 19 / 87
Análise de Algoritmos de Ordenação
Bubble Sort
262211 0704 30
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 20 / 87
Análise de Algoritmos de Ordenação
Bubble Sort
262211 0704 30
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 21 / 87
Análise de Algoritmos de Ordenação
Bubble Sort
262211 0704 30
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 22 / 87
Análise de Algoritmos de Ordenação
Bubble Sort
262211 0704 30
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 23 / 87
Análise de Algoritmos de Ordenação
Bubble Sort
262211 0704 30
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 24 / 87
Análise de Algoritmos de Ordenação
Bubble Sort
262211 0704 30
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 25 / 87
Análise de Algoritmos de Ordenação
Bubble Sort
262211 0704 30
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 26 / 87
Análise de Algoritmos de Ordenação
Bubble Sort
262211 0704 30
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 27 / 87
Análise de Algoritmos de Ordenação
Bubble Sort
262211 0704 30
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 28 / 87
Análise de Algoritmos de Ordenação
Bubble Sort
262211 0704 30
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 29 / 87
Análise de Algoritmos de Ordenação
Bubble Sort
262211 0704 30
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 30 / 87
Análise de Algoritmos de Ordenação
Bubble Sort
262211 0704 30
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 31 / 87
Análise de Algoritmos de Ordenação
Bubble Sort
262211 0704 30
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 32 / 87
Análise de Algoritmos de Ordenação
Bubble Sort
262211 0704 30
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 33 / 87
Análise de Algoritmos de Ordenação
Bubble Sort
262211 0704 30
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 34 / 87
Análise de Algoritmos de Ordenação
Bubble Sort
262211 0704 30
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 35 / 87
Análise de Algoritmos de Ordenação
Bubble Sort
262211 0704 30
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 36 / 87
Análise de Algoritmos de Ordenação
Bubble Sort
262211 0704 30
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 37 / 87
Análise de Algoritmos de Ordenação
Bubble Sort
2622110704 30
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 38 / 87
Análise de Algoritmos de Ordenação
Bubble Sort
2622110704 30
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 39 / 87
Análise de Algoritmos de Ordenação
Bubble Sort
2622110704 30
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 40 / 87
Análise de Algoritmos de Ordenação
Bubble Sort
2622110704 30
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 41 / 87
Análise de Algoritmos de Ordenação
Bubble Sort
2622110704 30
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 42 / 87
Análise de Algoritmos de Ordenação
Bubble Sort
2622110704 30
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 43 / 87
Análise de Algoritmos de Ordenação
Bubble Sort
2622110704 30
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 44 / 87
Análise de Algoritmos de Ordenação
Bubble Sort
2622110704 30
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 45 / 87
Análise de Algoritmos de Ordenação
Bubble Sort
2622110704 30
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 46 / 87
Análise de Algoritmos de Ordenação
Bubble Sort
2622110704 30
A cada iteração do laço mais externo do Bubble Sort, um número é
colocado na posição correta, do maior para o menor.
Então, seu laço externo executa n − 1 iterações, para colocar todos os
números em suas devidas posições.
Se não houver nenhum tratamento, o Buble Sort continua executando até
que seu laço de repetição externo complete n − 1 iterações.
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 47 / 87
Análise de Algoritmos de Ordenação
Selection Sort
262211 0704 30
menor 11
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 48 / 87
Análise de Algoritmos de Ordenação
Selection Sort
262211 0704 30
menor 11ocupar
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 49 / 87
Análise de Algoritmos de Ordenação
Selection Sort
262211 0704 30
menor 04ocupar
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 50 / 87
Análise de Algoritmos de Ordenação
Selection Sort
262211 0704 30
menor 04ocupar
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 51 / 87
Análise de Algoritmos de Ordenação
Selection Sort
262211 0704 30
menor 04ocupar
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 52 / 87
Análise de Algoritmos de Ordenação
Selection Sort
262211 0704 30
menor 04ocupar
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 53 / 87
Análise de Algoritmos de Ordenação
Selection Sort
262211 0704 30
menor 04ocupar
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 54 / 87
Análise de Algoritmos de Ordenação
Selection Sort
262211 0704 30
menor 04ocupar
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 55 / 87
Análise de Algoritmos de Ordenação
Selection Sort
262211 0704 30
menor 04ocupar
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 56 / 87
Análise de Algoritmos de Ordenação
Selection Sort
262211 0704 30
menor 11ocupar
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 57 / 87
Análise de Algoritmos de Ordenação
Selection Sort
262211 0704 30
menor 11ocupar
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 58 / 87
Análise de Algoritmos de Ordenação
Selection Sort
262211 0704 30
menor 11ocupar
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 59 / 87
Análise de Algoritmos de Ordenação
Selection Sort
262211 0704 30
menor 11ocupar
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 60 / 87
Análise de Algoritmos de Ordenação
Selection Sort
262211 0704 30
menor 07ocupar
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 61 / 87
Análise de Algoritmos de Ordenação
Selection Sort
262211 0704 30
menor 07ocupar
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 62 / 87
Análise de Algoritmos de Ordenação
Selection Sort
262211 0704 30
menor 07ocupar
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 63 / 87
Análise de Algoritmos de Ordenação
Selection Sort
262211 0704 30
menor 07ocupar
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 64 / 87
Análise de Algoritmos de Ordenação
Selection Sort
2622 110704 30
menor 07ocupar
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 65 / 87
Análise de Algoritmos de Ordenação
Selection Sort
2622 110704 30
menor 30ocupar
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 66 / 87
Análise de Algoritmos de Ordenação
Selection Sort
2622 110704 30
menor 30ocupar
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 67 / 87
Análise de Algoritmos de Ordenação
Selection Sort
2622 110704 30
menor 22ocupar
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 68 / 87
Análise de Algoritmos de Ordenação
Selection Sort
2622 110704 30
menor 22ocupar
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 69 / 87
Análise de Algoritmos de Ordenação
Selection Sort
2622 110704 30
menor 11ocupar
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 70 / 87
Análise de Algoritmos de Ordenação
Selection Sort
2622 110704 30
menor 11ocupar
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 71 / 87
Análise de Algoritmos de Ordenação
Selection Sort
2622 110704 30
menor 11ocupar
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 72 / 87
Análise de Algoritmos de Ordenação
Selection Sort
2622 110704 30
menor 11ocupar
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 73 / 87
Análise de Algoritmos de Ordenação
Selection Sort
2622110704 30
menor 11ocupar
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 74 / 87
Análise de Algoritmos de Ordenação
Selection Sort
2622110704 30
menor 22ocupar
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 75 / 87
Análise de Algoritmos de Ordenação
Selection Sort
2622110704 30
menor 22ocupar
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 76 / 87
Análise de Algoritmos de Ordenação
Selection Sort
2622110704 30
menor 22ocupar
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 77 / 87
Análise de Algoritmos de Ordenação
Selection Sort
2622110704 30
menor 22ocupar
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 78 / 87
Análise de Algoritmos de Ordenação
Selection Sort
2622110704 30
menor 22ocupar
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 79 / 87
Análise de Algoritmos de Ordenação
Selection Sort
2622110704 30
menor 30
ocupar
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 80 / 87
Análise de Algoritmos de Ordenação
Selection Sort
2622110704 30
menor 30
ocupar
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 81 / 87
Análise de Algoritmos de Ordenação
Selection Sort
2622110704 30
menor 26
ocupar
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 82 / 87
Análise de Algoritmos de Ordenação
Selection Sort
2622110704 30
menor 26
ocupar
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 83 / 87
Análise de Algoritmos de Ordenação
Selection Sort
2622110704 30
menor 26
ocupar
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 84 / 87
Análise de Algoritmos de Ordenação
Selection Sort
3022110704 26
menor 26
ocupar
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 85 / 87
Análise de Algoritmos de Ordenação
Selection Sort
3022110704 26
menor 26
ocupar
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 86 / 87
Análise de Algoritmos de Ordenação
Selection Sort
3022110704 26
Sheila Almeida (DAINF-UTFPR-PG) Algoritmos de Ordenação junho - 2018 87 / 87
