Slide - Ordenação por Seleção - 2023-2

1 Introdução à Computação II – 5954006 Introdução à Computação II 5954006 5. Algoritmos de Ordenação Prof. Renato Tinós Local: Depto. de Computação e Matemática (FFCLRP/USP) 2 Introdução à Computação II – 5954006 Principais Tópicos 5.1. Ordenação por Inserção 5.2. Ordenação por Seleção 5.3. Método da Bolha 5.4. Ordenação por Fusão 5.5. Heapsort 5.6. Quicksort 5.7. Considerações sobre o Problema de Ordenação 5.8. Ordenação em Tempo Linear 3 Introdução à Computação II – 5954006 5.2. Ordenação por Seleção • É um dos algoritmos mais simples de ordenação • O princípio de funcionamento é o seguinte 1. Selecionar o elemento que apresenta a chave de menor valor; 2. Trocá-lo com o primeiro elemento do vetor; 3. Repetir estas operações, envolvendo agora apenas os N-1 elementos restantes, depois os N-2 elementos, etc., até restar um só elemento, o maior deles. 4 Introdução à Computação II – 5954006 1. Selecionar o elemento que apresenta a chave de menor valor; 2. Trocá-lo com o primeiro elemento do vetor; 3. Repetir estas operações, envolvendo agora apenas os N-1 elementos restantes, depois os N-2 elementos, etc., até restar um só elemento, o maior deles. ... para i  1 até i  N-1 indice_menor  (o índice do menor elemento do vetor a={ a[i] a[i+1] a[i+2] ... a[N] } ) trocar a[i] com a[indice_menor] fim para ... 5.2. Ordenação por Seleção 5 Introdução à Computação II – 5954006 vetor inicial 45 56 12 43 95 19 8 67 i = 1 8 56 12 43 95 19 45 67 i = 2 8 12 56 43 95 19 45 67 i = 3 8 12 19 43 95 56 45 67 i = 4 8 12 19 43 95 56 45 67 i = 5 8 12 19 43 45 56 95 67 i = 6 8 12 19 43 45 56 95 67 i = 7 8 12 19 43 45 56 67 95 5.2. Ordenação por Seleção ... para i  1 até i  N-1 indice_menor  (índice do menor elemento do vetor a={ a[i] a[i+1] a[i+2] ... a[N] } ) trocar a[i] com a[indice_menor] fim para ... Exemplo 5.2.1. 6 Introdução à Computação II – 5954006 1 2 3 4 5 6 7 8 45 56 12 43 95 19 8 67 a N = 8 i indice_menor 5.2. Ordenação por Seleção ... para i  1 até i  N - 1 indice_menor  i para j  i + 1 até j  N se ( a[ j ] < a[ indice_menor ] ) indice_menor  j fim se fim para x  a [ i ] a [ i ]  a [ indice_menor ] a [ indice_menor ]  x fim para ... 7 Introdução à Computação II – 5954006 1 2 3 4 5 6 7 8 8 56 12 43 95 19 45 67 a N = 8 i indice_menor 5.2. Ordenação por Seleção ... para i  1 até i  N - 1 indice_menor  i para j  i + 1 até j  N se ( a[ j ] < a[ indice_menor ] ) indice_menor  j fim se fim para x  a [ i ] a [ i ]  a [ indice_menor ] a [ indice_menor ]  x fim para ... 8 Introdução à Computação II – 5954006 1 2 3 4 5 6 7 8 8 56 12 43 95 19 45 67 a N = 8 i indice_menor 5.2. Ordenação por Seleção ... para i  1 até i  N - 1 indice_menor  i para j  i + 1 até j  N se ( a[ j ] < a[ indice_menor ] ) indice_menor  j fim se fim para x  a [ i ] a [ i ]  a [ indice_menor ] a [ indice_menor ]  x fim para ... 9 Introdução à Computação II – 5954006 1 2 3 4 5 6 7 8 8 12 56 43 95 19 45 67 a N = 8 i indice_menor 5.2. Ordenação por Seleção ... para i  1 até i  N - 1 indice_menor  i para j  i + 1 até j  N se ( a[ j ] < a[ indice_menor ] ) indice_menor  j fim se fim para x  a [ i ] a [ i ]  a [ indice_menor ] a [ indice_menor ]  x fim para ... 10 Introdução à Computação II – 5954006 1 2 3 4 5 6 7 8 8 12 56 43 95 19 45 67 a N = 8 i indice_menor 5.2. Ordenação por Seleção ... para i  1 até i  N - 1 indice_menor  i para j  i + 1 até j  N se ( a[ j ] < a[ indice_menor ] ) indice_menor  j fim se fim para x  a [ i ] a [ i ]  a [ indice_menor ] a [ indice_menor ]  x fim para ... 11 Introdução à Computação II – 5954006 1 2 3 4 5 6 7 8 8 12 19 43 95 56 45 67 a N = 8 i indice_menor 5.2. Ordenação por Seleção ... para i  1 até i  N - 1 indice_menor  i para j  i + 1 até j  N se ( a[ j ] < a[ indice_menor ] ) indice_menor  j fim se fim para x  a [ i ] a [ i ]  a [ indice_menor ] a [ indice_menor ]  x fim para ... 12 Introdução à Computação II – 5954006 1 2 3 4 5 6 7 8 8 12 19 43 95 56 45 67 a N = 8 i indice_menor 5.2. Ordenação por Seleção ... para i  1 até i  N - 1 indice_menor  i para j  i + 1 até j  N se ( a[ j ] < a[ indice_menor ] ) indice_menor  j fim se fim para x  a [ i ] a [ i ]  a [ indice_menor ] a [ indice_menor ]  x fim para ... 13 Introdução à Computação II – 5954006 1 2 3 4 5 6 7 8 8 12 19 43 95 56 45 67 a N = 8 i indice_menor 5.2. Ordenação por Seleção ... para i  1 até i  N - 1 indice_menor  i para j  i + 1 até j  N se ( a[ j ] < a[ indice_menor ] ) indice_menor  j fim se fim para x  a [ i ] a [ i ]  a [ indice_menor ] a [ indice_menor ]  x fim para ... 14 Introdução à Computação II – 5954006 1 2 3 4 5 6 7 8 8 12 19 43 95 56 45 67 a N = 8 i indice_menor 5.2. Ordenação por Seleção ... para i  1 até i  N - 1 indice_menor  i para j  i + 1 até j  N se ( a[ j ] < a[ indice_menor ] ) indice_menor  j fim se fim para x  a [ i ] a [ i ]  a [ indice_menor ] a [ indice_menor ]  x fim para ... 15 Introdução à Computação II – 5954006 1 2 3 4 5 6 7 8 8 12 19 43 45 56 95 67 a N = 8 i indice_menor 5.2. Ordenação por Seleção ... para i  1 até i  N - 1 indice_menor  i para j  i + 1 até j  N se ( a[ j ] < a[ indice_menor ] ) indice_menor  j fim se fim para x  a [ i ] a [ i ]  a [ indice_menor ] a [ indice_menor ]  x fim para ... 16 Introdução à Computação II – 5954006 1 2 3 4 5 6 7 8 8 12 19 43 45 56 95 67 a N = 8 i indice_menor 5.2. Ordenação por Seleção ... para i  1 até i  N - 1 indice_menor  i para j  i + 1 até j  N se ( a[ j ] < a[ indice_menor ] ) indice_menor  j fim se fim para x  a [ i ] a [ i ]  a [ indice_menor ] a [ indice_menor ]  x fim para ... 17 Introdução à Computação II – 5954006 1 2 3 4 5 6 7 8 8 12 19 43 45 56 95 67 a N = 8 i indice_menor 5.2. Ordenação por Seleção ... para i  1 até i  N - 1 indice_menor  i para j  i + 1 até j  N se ( a[ j ] < a[ indice_menor ] ) indice_menor  j fim se fim para x  a [ i ] a [ i ]  a [ indice_menor ] a [ indice_menor ]  x fim para ... 18 Introdução à Computação II – 5954006 1 2 3 4 5 6 7 8 8 12 19 43 45 56 95 67 a N = 8 i indice_menor 5.2. Ordenação por Seleção ... para i  1 até i  N - 1 indice_menor  i para j  i + 1 até j  N se ( a[ j ] < a[ indice_menor ] ) indice_menor  j fim se fim para x  a [ i ] a [ i ]  a [ indice_menor ] a [ indice_menor ]  x fim para ... 19 Introdução à Computação II – 5954006 1 2 3 4 5 6 7 8 8 12 19 43 45 56 67 95 a N = 8 i indice_menor 5.2. Ordenação por Seleção ... para i  1 até i  N - 1 indice_menor  i para j  i + 1 até j  N se ( a[ j ] < a[ indice_menor ] ) indice_menor  j fim se fim para x  a [ i ] a [ i ]  a [ indice_menor ] a [ indice_menor ]  x fim para ... 20 Introdução à Computação II – 5954006 1 2 3 4 5 6 7 8 8 12 19 43 45 56 67 95 a N = 8 Vetor ordenado ... para i  1 até i  N - 1 indice_menor  i para j  i + 1 até j  N se ( a[ j ] < a[ indice_menor ] ) indice_menor  j fim se fim para x  a [ i ] a [ i ]  a [ indice_menor ] a [ indice_menor ]  x fim para ... 5.2. Ordenação por Seleção 21 Introdução à Computação II – 5954006 ... para i  1 até i  N - 1 indice_menor  i para j  i + 1 até j  N se ( a[ j ] < a[ indice_menor ] ) indice_menor  j fim se fim para x  a [ i ] a [ i ]  a [ indice_menor ] a [ indice_menor ]  x fim para ... 5.2. Ordenação por Seleção 22 Introdução à Computação II – 5954006 • Análise ▪ Os números C (comparações entre chaves) e M (movimentações de registros) independem da ordem do vetor ➢Assim, esse método apresenta comportamento menos natural que o da inserção direta – O método da inserção direta realiza mais operações para vetores “mais desordenados” ▪ A grande vantagem é o pequeno número de movimentações entre registros ( ) ) ( 2 1 2 1 1 2 1 1 1 O N N N i N C N i N i N i j = − = − = =    − = − = + = ) ( )1 (3 3 1 1 O N N M N i = − = =  − = 5.2. Ordenação por Seleção 23 Introdução à Computação II – 5954006 Exercício 5.2.1. Utilizando ordenação por seleção, obtenha o número de comparações e movimentações em cada passo para os seguintes vetores a) [ 45 56 12 43 95 19 8 67 ] b) [ 8 12 19 43 45 56 67 95 ] c) [ 95 67 56 45 43 19 12 8 ] d) [ 19 12 8 45 43 56 67 95 ] 5.2. Ordenação por Seleção 24 Introdução à Computação II – 5954006 i Ci Mi 45 56 12 43 95 19 8 67 1 7 3 8 56 12 43 95 19 45 67 2 6 3 8 12 56 43 95 19 45 67 3 5 3 8 12 19 43 95 56 45 67 4 4 3 8 12 19 43 95 56 45 67 5 3 3 8 12 19 43 45 56 95 67 6 2 3 8 12 19 43 45 56 95 67 7 1 3 8 12 19 43 45 56 67 95 28 21 i Ci Mi 8 12 19 43 45 56 67 95 1 7 3 8 12 19 43 45 56 67 95 2 6 3 8 12 19 43 45 56 67 95 3 5 3 8 12 19 43 45 56 67 95 4 4 3 8 12 19 43 45 56 67 95 5 3 3 8 12 19 43 45 56 67 95 6 2 3 8 12 19 43 45 56 67 95 7 1 3 8 12 19 43 45 56 67 95 28 21 i Ci Mi 95 67 56 45 43 19 12 8 1 7 3 8 67 56 45 43 19 12 95 2 6 3 8 12 56 45 43 19 67 95 3 5 3 8 12 19 45 43 56 67 95 4 4 3 8 12 19 43 45 56 67 95 5 3 3 8 12 19 43 45 56 67 95 6 2 3 8 12 19 43 45 56 67 95 7 1 3 8 12 19 43 45 56 67 95 28 21 i Ci Mi 19 12 8 45 43 56 67 95 1 7 3 8 12 19 45 43 56 67 95 2 6 3 8 12 19 45 43 56 67 95 3 5 3 8 12 19 45 43 56 67 95 4 4 3 8 12 19 43 45 56 67 95 5 3 3 8 12 19 43 45 56 67 95 6 2 3 8 12 19 43 45 56 67 95 7 1 3 8 12 19 43 45 56 67 95 28 21 5.2. Ordenação por Seleção Exercício 5.2.1. Solução 25 Introdução à Computação II – 5954006 Comentários • Agradecimentos ◼ Parte do material desta apresentação foi obtida através de slides da disciplina de Introdução à Computação II ministrada pelo Prof. José Augusto Baranauskas