Algoritmos de Ordenação - Sheila AlmeidaAnálise de Algoritmos de Ordenação Bubble Sort 04 07 11...

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