·

Matemática Aplicada a Negócios ·

Introdução à Computação 2

· 2023/2

Envie sua pergunta para a IA e receba a resposta na hora

Equipe Meu Guru

Prefere sua atividade resolvida por um tutor especialista?

  • Receba resolvida até o seu prazo
  • Converse com o tutor pelo chat
  • Garantia de 7 dias contra erros

Texto de pré-visualização

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 5. Algoritmos de Ordenação 5.1. Ordenação por Inserção 5.2. Ordenação por Seleção 5.3. Método da Bolha 5.3.1. Bubblesort 5.3.2. Shakesort 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 • Método da Bolha ▪ Utiliza a permutação entre os registros do conjunto ▪ Efetuam-se varreduras repetidas sobre o vetor, deslocando-se, a cada passo, o menor dos elementos do conjunto que restou para a sua extremidade esquerda ▪ Se o vetor (conjunto de registros) for considerado do tipo coluna, os elementos (registros) podem ser comparados a bolhas em um tanque de água, com densidades proporcionais ao valor das respectivas chaves ➢cada varredura efetuada sobre o vetor resulta na ascensão de uma bolha para o seu nível apropriado, de acordo com sua densidade 5.3. Método da Bolha 4 Introdução à Computação II – 5954006 45 56 12 43 95 19 8 67 a N = 8 1 2 3 4 5 6 7 8 5.3.1. Bubblesort ... para i  2 até i  N , com passo i  i+1 para j  N até j  i , com passo j  j-1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x fim se fim para fim para ... Exemplo 5.3.1. 5 Introdução à Computação II – 5954006 45 56 12 43 95 19 8 67 a N = 8 i 1 2 3 4 5 6 7 8 j j -1 5.3.1. Bubblesort ... para i  2 até i  N , com passo i  i+1 para j  N até j  i , com passo j  j-1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x fim se fim para fim para ... 6 Introdução à Computação II – 5954006 45 56 12 43 95 19 8 67 a N = 8 i 1 2 3 4 5 6 7 8 j j -1 5.3.1. Bubblesort ... para i  2 até i  N , com passo i  i+1 para j  N até j  i , com passo j  j-1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x fim se fim para fim para ... 7 Introdução à Computação II – 5954006 45 56 12 43 95 8 19 67 a N = 8 i 1 2 3 4 5 6 7 8 j j -1 5.3.1. Bubblesort ... para i  2 até i  N , com passo i  i+1 para j  N até j  i , com passo j  j-1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x fim se fim para fim para ... 8 Introdução à Computação II – 5954006 45 56 12 43 95 8 19 67 a N = 8 i 1 2 3 4 5 6 7 8 j j -1 5.3.1. Bubblesort ... para i  2 até i  N , com passo i  i+1 para j  N até j  i , com passo j  j-1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x fim se fim para fim para ... 9 Introdução à Computação II – 5954006 45 56 12 43 8 95 19 67 a N = 8 i 1 2 3 4 5 6 7 8 j j -1 5.3.1. Bubblesort ... para i  2 até i  N , com passo i  i+1 para j  N até j  i , com passo j  j-1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x fim se fim para fim para ... 10 Introdução à Computação II – 5954006 45 56 12 43 8 95 19 67 a N = 8 i 1 2 3 4 5 6 7 8 j j -1 5.3.1. Bubblesort ... para i  2 até i  N , com passo i  i+1 para j  N até j  i , com passo j  j-1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x fim se fim para fim para ... 11 Introdução à Computação II – 5954006 45 56 12 8 43 95 19 67 a N = 8 i 1 2 3 4 5 6 7 8 j j -1 5.3.1. Bubblesort ... para i  2 até i  N , com passo i  i+1 para j  N até j  i , com passo j  j-1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x fim se fim para fim para ... 12 Introdução à Computação II – 5954006 45 56 12 8 43 95 19 67 a N = 8 i 1 2 3 4 5 6 7 8 j j -1 5.3.1. Bubblesort ... para i  2 até i  N , com passo i  i+1 para j  N até j  i , com passo j  j-1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x fim se fim para fim para ... 13 Introdução à Computação II – 5954006 45 56 8 12 43 95 19 67 a N = 8 i 1 2 3 4 5 6 7 8 j j -1 5.3.1. Bubblesort ... para i  2 até i  N , com passo i  i+1 para j  N até j  i , com passo j  j-1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x fim se fim para fim para ... 14 Introdução à Computação II – 5954006 45 56 8 12 43 95 19 67 a N = 8 i 1 2 3 4 5 6 7 8 j j -1 5.3.1. Bubblesort ... para i  2 até i  N , com passo i  i+1 para j  N até j  i , com passo j  j-1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x fim se fim para fim para ... 15 Introdução à Computação II – 5954006 45 8 56 12 43 95 19 67 a N = 8 i 1 2 3 4 5 6 7 8 j j -1 5.3.1. Bubblesort ... para i  2 até i  N , com passo i  i+1 para j  N até j  i , com passo j  j-1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x fim se fim para fim para ... 16 Introdução à Computação II – 5954006 45 8 56 12 43 95 19 67 a N = 8 i 1 2 3 4 5 6 7 8 j j -1 5.3.1. Bubblesort ... para i  2 até i  N , com passo i  i+1 para j  N até j  i , com passo j  j-1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x fim se fim para fim para ... 17 Introdução à Computação II – 5954006 8 45 56 12 43 95 19 67 a N = 8 i 1 2 3 4 5 6 7 8 j j -1 5.3.1. Bubblesort ... para i  2 até i  N , com passo i  i+1 para j  N até j  i , com passo j  j-1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x fim se fim para fim para ... 18 Introdução à Computação II – 5954006 8 45 56 12 43 95 19 67 a N = 8 i 1 3 4 5 6 7 8 2 5.3.1. Bubblesort ... para i  2 até i  N , com passo i  i+1 para j  N até j  i , com passo j  j-1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x fim se fim para fim para ... Término da primeira passagem (i=2). Note que o elemento 8, mais “leve” (menor valor) encontra-se na extremidade superior do vetor (ou extremidade esquerda se visto na horizontal) 19 Introdução à Computação II – 5954006 8 45 56 12 43 95 19 67 a N = 8 i 1 2 3 4 5 6 7 8 j j -1 5.3.1. Bubblesort ... para i  2 até i  N , com passo i  i+1 para j  N até j  i , com passo j  j-1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x fim se fim para fim para ... 20 Introdução à Computação II – 5954006 8 45 56 12 43 95 19 67 a N = 8 i 1 2 3 4 5 6 7 8 j j -1 5.3.1. Bubblesort ... para i  2 até i  N , com passo i  i+1 para j  N até j  i , com passo j  j-1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x fim se fim para fim para ... 21 Introdução à Computação II – 5954006 8 45 56 12 43 19 95 67 a N = 8 i 1 2 3 4 5 6 7 8 j j -1 5.3.1. Bubblesort ... para i  2 até i  N , com passo i  i+1 para j  N até j  i , com passo j  j-1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x fim se fim para fim para ... 22 Introdução à Computação II – 5954006 8 45 56 12 43 19 95 67 a N = 8 i 1 2 3 4 5 6 7 8 j j -1 5.3.1. Bubblesort ... para i  2 até i  N , com passo i  i+1 para j  N até j  i , com passo j  j-1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x fim se fim para fim para ... 23 Introdução à Computação II – 5954006 8 45 56 12 19 43 95 67 a N = 8 i 1 2 3 4 5 6 7 8 j j -1 5.3.1. Bubblesort ... para i  2 até i  N , com passo i  i+1 para j  N até j  i , com passo j  j-1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x fim se fim para fim para ... 24 Introdução à Computação II – 5954006 8 45 56 12 19 43 95 67 a N = 8 i 1 2 3 4 5 6 7 8 j j -1 5.3.1. Bubblesort ... para i  2 até i  N , com passo i  i+1 para j  N até j  i , com passo j  j-1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x fim se fim para fim para ... 25 Introdução à Computação II – 5954006 8 45 56 12 19 43 95 67 a N = 8 i 1 2 3 4 5 6 7 8 j j -1 5.3.1. Bubblesort ... para i  2 até i  N , com passo i  i+1 para j  N até j  i , com passo j  j-1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x fim se fim para fim para ... 26 Introdução à Computação II – 5954006 8 45 12 56 19 43 95 67 a N = 8 i 1 2 3 4 5 6 7 8 j j -1 5.3.1. Bubblesort ... para i  2 até i  N , com passo i  i+1 para j  N até j  i , com passo j  j-1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x fim se fim para fim para ... 27 Introdução à Computação II – 5954006 8 45 12 56 19 43 95 67 a N = 8 i 1 2 3 4 5 6 7 8 j j -1 5.3.1. Bubblesort ... para i  2 até i  N , com passo i  i+1 para j  N até j  i , com passo j  j-1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x fim se fim para fim para ... 28 Introdução à Computação II – 5954006 8 12 45 56 19 43 95 67 a N = 8 i 1 2 3 4 5 6 7 8 j j -1 5.3.1. Bubblesort ... para i  2 até i  N , com passo i  i+1 para j  N até j  i , com passo j  j-1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x fim se fim para fim para ... 29 Introdução à Computação II – 5954006 8 12 45 56 19 43 95 67 a N = 8 i 1 2 3 4 5 6 7 8 Término da segunda passagem (i=3) 5.3.1. Bubblesort ... para i  2 até i  N , com passo i  i+1 para j  N até j  i , com passo j  j-1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x fim se fim para fim para ... 30 Introdução à Computação II – 5954006 8 12 45 56 19 43 95 67 a N = 8 i 1 2 3 4 5 6 7 8 j j -1 5.3.1. Bubblesort ... para i  2 até i  N , com passo i  i+1 para j  N até j  i , com passo j  j-1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x fim se fim para fim para ... 31 Introdução à Computação II – 5954006 8 12 45 56 19 43 67 95 a N = 8 i 1 2 3 4 5 6 7 8 j j -1 5.3.1. Bubblesort ... para i  2 até i  N , com passo i  i+1 para j  N até j  i , com passo j  j-1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x fim se fim para fim para ... 32 Introdução à Computação II – 5954006 8 12 45 56 19 43 67 95 a N = 8 i 1 2 3 4 5 6 7 8 j j -1 5.3.1. Bubblesort ... para i  2 até i  N , com passo i  i+1 para j  N até j  i , com passo j  j-1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x fim se fim para fim para ... 33 Introdução à Computação II – 5954006 8 12 45 56 19 43 67 95 a N = 8 i 1 2 3 4 5 6 7 8 j j -1 5.3.1. Bubblesort ... para i  2 até i  N , com passo i  i+1 para j  N até j  i , com passo j  j-1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x fim se fim para fim para ... 34 Introdução à Computação II – 5954006 8 12 45 56 19 43 67 95 a N = 8 i 1 2 3 4 5 6 7 8 j j -1 5.3.1. Bubblesort ... para i  2 até i  N , com passo i  i+1 para j  N até j  i , com passo j  j-1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x fim se fim para fim para ... 35 Introdução à Computação II – 5954006 8 12 45 19 56 43 67 95 a N = 8 i 1 2 3 4 5 6 7 8 j j -1 5.3.1. Bubblesort ... para i  2 até i  N , com passo i  i+1 para j  N até j  i , com passo j  j-1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x fim se fim para fim para ... 36 Introdução à Computação II – 5954006 8 12 45 19 56 43 67 95 a N = 8 i 1 2 3 4 5 6 7 8 j j -1 5.3.1. Bubblesort ... para i  2 até i  N , com passo i  i+1 para j  N até j  i , com passo j  j-1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x fim se fim para fim para ... 37 Introdução à Computação II – 5954006 8 12 19 45 56 43 67 95 a N = 8 i 1 2 3 4 5 6 7 8 j j -1 5.3.1. Bubblesort ... para i  2 até i  N , com passo i  i+1 para j  N até j  i , com passo j  j-1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x fim se fim para fim para ... 38 Introdução à Computação II – 5954006 8 12 19 45 56 43 67 95 a N = 8 i 1 2 3 4 5 6 7 8 Término da passagem i=4 5.3.1. Bubblesort ... para i  2 até i  N , com passo i  i+1 para j  N até j  i , com passo j  j-1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x fim se fim para fim para ... 39 Introdução à Computação II – 5954006 8 12 19 45 56 43 67 95 a N = 8 i 1 2 3 4 5 6 7 8 j j -1 5.3.1. Bubblesort ... para i  2 até i  N , com passo i  i+1 para j  N até j  i , com passo j  j-1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x fim se fim para fim para ... 40 Introdução à Computação II – 5954006 8 12 19 45 56 43 67 95 a N = 8 i 1 2 3 4 5 6 7 8 j j -1 5.3.1. Bubblesort ... para i  2 até i  N , com passo i  i+1 para j  N até j  i , com passo j  j-1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x fim se fim para fim para ... 41 Introdução à Computação II – 5954006 8 12 19 45 56 43 67 95 a N = 8 i 1 2 3 4 5 6 7 8 j j -1 5.3.1. Bubblesort ... para i  2 até i  N , com passo i  i+1 para j  N até j  i , com passo j  j-1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x fim se fim para fim para ... 42 Introdução à Computação II – 5954006 8 12 19 45 43 56 67 95 a N = 8 i 1 2 3 4 5 6 7 8 j j -1 5.3.1. Bubblesort ... para i  2 até i  N , com passo i  i+1 para j  N até j  i , com passo j  j-1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x fim se fim para fim para ... 43 Introdução à Computação II – 5954006 8 12 19 45 43 56 67 95 a N = 8 i 1 2 3 4 5 6 7 8 j j -1 5.3.1. Bubblesort ... para i  2 até i  N , com passo i  i+1 para j  N até j  i , com passo j  j-1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x fim se fim para fim para ... 44 Introdução à Computação II – 5954006 8 12 19 43 45 56 67 95 a N = 8 i 1 2 3 4 5 6 7 8 j j -1 5.3.1. Bubblesort ... para i  2 até i  N , com passo i  i+1 para j  N até j  i , com passo j  j-1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x fim se fim para fim para ... 45 Introdução à Computação II – 5954006 8 12 19 43 45 56 67 95 a N = 8 i 1 2 3 4 5 6 7 8 Término da passagem i=5 5.3.1. Bubblesort ... para i  2 até i  N , com passo i  i+1 para j  N até j  i , com passo j  j-1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x fim se fim para fim para ... 46 Introdução à Computação II – 5954006 8 12 19 43 45 56 67 95 a N = 8 i 1 2 3 4 5 6 7 8 j j -1 5.3.1. Bubblesort ... para i  2 até i  N , com passo i  i+1 para j  N até j  i , com passo j  j-1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x fim se fim para fim para ... 47 Introdução à Computação II – 5954006 8 12 19 43 45 56 67 95 a N = 8 i 1 2 3 4 5 6 7 8 j j -1 5.3.1. Bubblesort ... para i  2 até i  N , com passo i  i+1 para j  N até j  i , com passo j  j-1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x fim se fim para fim para ... 48 Introdução à Computação II – 5954006 8 12 19 43 45 56 67 95 a N = 8 i 1 2 3 4 5 6 7 8 j j -1 5.3.1. Bubblesort ... para i  2 até i  N , com passo i  i+1 para j  N até j  i , com passo j  j-1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x fim se fim para fim para ... 49 Introdução à Computação II – 5954006 8 12 19 43 45 56 67 95 a N = 8 i 1 2 3 4 5 6 7 8 Término da passagem i=6. Note que não houve permutação de elementos nesta passagem. 5.3.1. Bubblesort ... para i  2 até i  N , com passo i  i+1 para j  N até j  i , com passo j  j-1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x fim se fim para fim para ... 50 Introdução à Computação II – 5954006 8 12 19 43 45 56 67 95 a N = 8 i 1 2 3 4 5 6 7 8 j j -1 5.3.1. Bubblesort ... para i  2 até i  N , com passo i  i+1 para j  N até j  i , com passo j  j-1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x fim se fim para fim para ... 51 Introdução à Computação II – 5954006 8 12 19 43 45 56 67 95 a N = 8 i 1 2 3 4 5 6 7 8 j j -1 5.3.1. Bubblesort ... para i  2 até i  N , com passo i  i+1 para j  N até j  i , com passo j  j-1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x fim se fim para fim para ... 52 Introdução à Computação II – 5954006 8 12 19 43 45 56 67 95 a N = 8 i 1 2 3 4 5 6 7 8 Término da passagem i=7. Note que não houve permutação de elementos nesta passagem. 5.3.1. Bubblesort ... para i  2 até i  N , com passo i  i+1 para j  N até j  i , com passo j  j-1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x fim se fim para fim para ... 53 Introdução à Computação II – 5954006 8 12 19 43 45 56 67 95 a N = 8 i 1 2 3 4 5 6 7 8 j j -1 5.3.1. Bubblesort ... para i  2 até i  N , com passo i  i+1 para j  N até j  i , com passo j  j-1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x fim se fim para fim para ... 54 Introdução à Computação II – 5954006 8 12 19 43 45 56 67 95 a N = 8 i 1 2 3 4 5 6 7 8 Término da passagem i=8. Note que não houve permutação de elementos nesta passagem. Vetor ordenado 5.3.1. Bubblesort ... para i  2 até i  N , com passo i  i+1 para j  N até j  i , com passo j  j-1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x fim se fim para fim para ... 55 Introdução à Computação II – 5954006 • Análise ▪ Os números C de comparações entre chaves e M de movimentações entre registros são ( ) ) ( 2 1 1 2 2 2 2 O N N N i N C N i N i N i j = − = − + = =   = = = )1( 0 mín O M = = ) ( 2 3 2 méd O N C M = = ) ( 3 2 máx O N C M = = 5.3.1. Bubblesort 56 Introdução à Computação II – 5954006 Exercício 5.3.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.3.1. Bubblesort 57 Introdução à Computação II – 5954006 i Ci Mi 45 56 12 43 95 19 8 67 2 7 18 8 45 56 12 43 95 19 67 3 6 12 8 12 45 56 19 43 95 67 4 5 9 8 12 19 45 56 43 67 95 5 4 6 8 12 19 43 45 56 67 95 6 3 0 8 12 19 43 45 56 67 95 7 2 0 8 12 19 43 45 56 67 95 8 1 0 8 12 19 43 45 56 67 95 28 45 i Ci Mi 8 12 19 43 45 56 67 95 2 7 0 8 12 19 43 45 56 67 95 3 6 0 8 12 19 43 45 56 67 95 4 5 0 8 12 19 43 45 56 67 95 5 4 0 8 12 19 43 45 56 67 95 6 3 0 8 12 19 43 45 56 67 95 7 2 0 8 12 19 43 45 56 67 95 8 1 0 8 12 19 43 45 56 67 95 28 0 i Ci Mi 95 67 56 45 43 19 12 8 2 7 21 8 95 67 56 45 43 19 12 3 6 18 8 12 95 67 56 45 43 19 4 5 15 8 12 19 95 67 56 45 43 5 4 12 8 12 19 43 95 67 56 45 6 3 9 8 12 19 43 45 95 67 56 7 2 6 8 12 19 43 45 56 95 67 8 1 3 8 12 19 43 45 56 67 95 28 84 i Ci Mi 19 12 8 45 43 56 67 95 2 7 9 8 19 12 43 45 56 67 95 3 6 3 8 12 19 43 45 56 67 95 4 5 0 8 12 19 43 45 56 67 95 5 4 0 8 12 19 43 45 56 67 95 6 3 0 8 12 19 43 45 56 67 95 7 2 0 8 12 19 43 45 56 67 95 8 1 0 8 12 19 43 45 56 67 95 28 12 5.3.1. Bubblesort Exercício 5.3.1. Solução 58 Introdução à Computação II – 5954006 • No vetor exemplo, pode-se observar que os três últimos passos do algoritmo não afetam a ordem dos elementos do vetor, pois estes já se encontram ordenados • Uma técnica para melhorar o algoritmo Bubblesort consiste em manter uma indicação informando se houve ou não a ocorrência de uma permutação, para determinar antecipadamente o término do algoritmo • Entretanto, mesmo essa melhoria pode ser por sua vez aperfeiçoada, guardando-se não a simples informação da ocorrência de uma permutação, mas a posição (índice) do vetor em que ocorreu a última permutação realizada 5.3.2. Shakesort 59 Introdução à Computação II – 5954006 • Assimetria: uma bolha única, colocada de modo incorreto, na extremidade mais densa do vetor, cujos demais elementos estejam ordenados, será posicionada corretamente em um único passo, mas um elemento incorretamente posicionado na extremidade menos densa irá deslocar-se de apenas uma posição por vez em direção à sua correta posição. Por exemplo, o vetor v = [ 12 19 43 45 56 67 95 8] • é ordenado pelo método Bubblesort aperfeiçoado em um único passo, mas o vetor v = [ 95 8 12 19 43 45 56 67] • requer sete passos para a sua ordenação. • Esta assimetria não natural sugere uma terceira melhoria: alternar a direção dos sucessivos passos de ordenação: Shakersort (ou Agitação) 5.3.2. Shakesort 60 Introdução à Computação II – 5954006 45 56 12 43 95 19 8 67 a N = 8 1 2 3 4 5 6 7 8 5.3.2. Shakesort ... L  2; R  N; k  N ; faça para j  R até j  L , com passo j  j -1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para L  k + 1 para j  L até j  R , com passo j  j+1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para R  k - 1 enquanto ( L ≤ R ) ... Exemplo 5.3.2. 61 Introdução à Computação II – 5954006 45 56 12 43 95 19 8 67 a N = 8 1 2 3 4 5 6 7 8 L j j -1 R k 5.3.2. Shakesort ... L  2; R  N; k  N ; faça para j  R até j  L , com passo j  j -1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para L  k + 1 para j  L até j  R , com passo j  j+1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para R  k - 1 enquanto ( L ≤ R ) ... 62 Introdução à Computação II – 5954006 45 56 12 43 95 19 8 67 a N = 8 1 2 3 4 5 6 7 8 L j j -1 R k 5.3.2. Shakesort ... L  2; R  N; k  N ; faça para j  R até j  L , com passo j  j -1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para L  k + 1 para j  L até j  R , com passo j  j+1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para R  k - 1 enquanto ( L ≤ R ) ... 63 Introdução à Computação II – 5954006 45 56 12 43 95 8 19 67 a N = 8 1 2 3 4 5 6 7 8 L j j -1 R k 5.3.2. Shakesort ... L  2; R  N; k  N ; faça para j  R até j  L , com passo j  j -1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para L  k + 1 para j  L até j  R , com passo j  j+1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para R  k - 1 enquanto ( L ≤ R ) ... 64 Introdução à Computação II – 5954006 45 56 12 43 95 8 19 67 a N = 8 1 2 3 4 5 6 7 8 L j j -1 R k 5.3.2. Shakesort ... L  2; R  N; k  N ; faça para j  R até j  L , com passo j  j -1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para L  k + 1 para j  L até j  R , com passo j  j+1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para R  k - 1 enquanto ( L ≤ R ) ... 65 Introdução à Computação II – 5954006 45 56 12 43 8 95 19 67 a N = 8 1 2 3 4 5 6 7 8 L j j -1 R k 5.3.2. Shakesort ... L  2; R  N; k  N ; faça para j  R até j  L , com passo j  j -1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para L  k + 1 para j  L até j  R , com passo j  j+1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para R  k - 1 enquanto ( L ≤ R ) ... 66 Introdução à Computação II – 5954006 45 56 12 43 8 95 19 67 a N = 8 1 2 3 4 5 6 7 8 L j j -1 R k 5.3.2. Shakesort ... L  2; R  N; k  N ; faça para j  R até j  L , com passo j  j -1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para L  k + 1 para j  L até j  R , com passo j  j+1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para R  k - 1 enquanto ( L ≤ R ) ... 67 Introdução à Computação II – 5954006 45 56 12 8 43 95 19 67 a N = 8 1 2 3 4 5 6 7 8 L j j -1 R k 5.3.2. Shakesort ... L  2; R  N; k  N ; faça para j  R até j  L , com passo j  j -1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para L  k + 1 para j  L até j  R , com passo j  j+1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para R  k - 1 enquanto ( L ≤ R ) ... 68 Introdução à Computação II – 5954006 45 56 12 8 43 95 19 67 a N = 8 1 2 3 4 5 6 7 8 L j j -1 R k 5.3.2. Shakesort ... L  2; R  N; k  N ; faça para j  R até j  L , com passo j  j -1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para L  k + 1 para j  L até j  R , com passo j  j+1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para R  k - 1 enquanto ( L ≤ R ) ... 69 Introdução à Computação II – 5954006 45 56 8 12 43 95 19 67 a N = 8 1 2 3 4 5 6 7 8 L j j -1 R k 5.3.2. Shakesort ... L  2; R  N; k  N ; faça para j  R até j  L , com passo j  j -1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para L  k + 1 para j  L até j  R , com passo j  j+1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para R  k - 1 enquanto ( L ≤ R ) ... 70 Introdução à Computação II – 5954006 45 56 8 12 43 95 19 67 a N = 8 1 2 3 4 5 6 7 8 L j j -1 R k 5.3.2. Shakesort ... L  2; R  N; k  N ; faça para j  R até j  L , com passo j  j -1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para L  k + 1 para j  L até j  R , com passo j  j+1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para R  k - 1 enquanto ( L ≤ R ) ... 71 Introdução à Computação II – 5954006 45 8 56 12 43 95 19 67 a N = 8 1 2 3 4 5 6 7 8 L j j -1 R k 5.3.2. Shakesort ... L  2; R  N; k  N ; faça para j  R até j  L , com passo j  j -1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para L  k + 1 para j  L até j  R , com passo j  j+1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para R  k - 1 enquanto ( L ≤ R ) ... 72 Introdução à Computação II – 5954006 45 8 56 12 43 95 19 67 a N = 8 1 2 3 4 5 6 7 8 L j j -1 R k 5.3.2. Shakesort ... L  2; R  N; k  N ; faça para j  R até j  L , com passo j  j -1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para L  k + 1 para j  L até j  R , com passo j  j+1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para R  k - 1 enquanto ( L ≤ R ) ... 73 Introdução à Computação II – 5954006 8 45 56 12 43 95 19 67 a N = 8 1 2 3 4 5 6 7 8 L j j -1 R k 5.3.2. Shakesort ... L  2; R  N; k  N ; faça para j  R até j  L , com passo j  j -1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para L  k + 1 para j  L até j  R , com passo j  j+1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para R  k - 1 enquanto ( L ≤ R ) ... 74 Introdução à Computação II – 5954006 8 45 56 12 43 95 19 67 a N = 8 1 2 3 4 5 6 7 8 L R k Término da 1ª “subida” 5.3.2. Shakesort ... L  2; R  N; k  N ; faça para j  R até j  L , com passo j  j -1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para L  k + 1 para j  L até j  R , com passo j  j+1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para R  k - 1 enquanto ( L ≤ R ) ... 75 Introdução à Computação II – 5954006 8 45 56 12 43 95 19 67 a N = 8 1 2 3 4 5 6 7 8 L R k Início da 1ª “descida” j j -1 5.3.2. Shakesort ... L  2; R  N; k  N ; faça para j  R até j  L , com passo j  j -1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para L  k + 1 para j  L até j  R , com passo j  j+1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para R  k - 1 enquanto ( L ≤ R ) ... 76 Introdução à Computação II – 5954006 8 45 56 12 43 95 19 67 a N = 8 1 2 3 4 5 6 7 8 L R k j j -1 5.3.2. Shakesort ... L  2; R  N; k  N ; faça para j  R até j  L , com passo j  j -1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para L  k + 1 para j  L até j  R , com passo j  j+1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para R  k - 1 enquanto ( L ≤ R ) ... 77 Introdução à Computação II – 5954006 8 45 12 56 43 95 19 67 a N = 8 1 2 3 4 5 6 7 8 L R k j j -1 5.3.2. Shakesort ... L  2; R  N; k  N ; faça para j  R até j  L , com passo j  j -1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para L  k + 1 para j  L até j  R , com passo j  j+1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para R  k - 1 enquanto ( L ≤ R ) ... 78 Introdução à Computação II – 5954006 8 45 12 56 43 95 19 67 a N = 8 1 2 3 4 5 6 7 8 L R k j j -1 5.3.2. Shakesort ... L  2; R  N; k  N ; faça para j  R até j  L , com passo j  j -1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para L  k + 1 para j  L até j  R , com passo j  j+1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para R  k - 1 enquanto ( L ≤ R ) ... 79 Introdução à Computação II – 5954006 8 45 12 43 56 95 19 67 a N = 8 1 2 3 4 5 6 7 8 L R k j j -1 5.3.2. Shakesort ... L  2; R  N; k  N ; faça para j  R até j  L , com passo j  j -1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para L  k + 1 para j  L até j  R , com passo j  j+1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para R  k - 1 enquanto ( L ≤ R ) ... 80 Introdução à Computação II – 5954006 8 45 12 43 56 95 19 67 a N = 8 1 2 3 4 5 6 7 8 L R k j j -1 5.3.2. Shakesort ... L  2; R  N; k  N ; faça para j  R até j  L , com passo j  j -1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para L  k + 1 para j  L até j  R , com passo j  j+1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para R  k - 1 enquanto ( L ≤ R ) ... 81 Introdução à Computação II – 5954006 8 45 12 43 56 95 19 67 a N = 8 1 2 3 4 5 6 7 8 L R k j j -1 5.3.2. Shakesort ... L  2; R  N; k  N ; faça para j  R até j  L , com passo j  j -1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para L  k + 1 para j  L até j  R , com passo j  j+1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para R  k - 1 enquanto ( L ≤ R ) ... 82 Introdução à Computação II – 5954006 8 45 12 43 56 19 95 67 a N = 8 1 2 3 4 5 6 7 8 L R k j j -1 5.3.2. Shakesort ... L  2; R  N; k  N ; faça para j  R até j  L , com passo j  j -1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para L  k + 1 para j  L até j  R , com passo j  j+1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para R  k - 1 enquanto ( L ≤ R ) ... 83 Introdução à Computação II – 5954006 8 45 12 43 56 19 95 67 a N = 8 1 2 3 4 5 6 7 8 L R k j j -1 5.3.2. Shakesort ... L  2; R  N; k  N ; faça para j  R até j  L , com passo j  j -1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para L  k + 1 para j  L até j  R , com passo j  j+1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para R  k - 1 enquanto ( L ≤ R ) ... 84 Introdução à Computação II – 5954006 8 45 12 43 56 19 67 95 a N = 8 1 2 3 4 5 6 7 8 L R k j j -1 5.3.2. Shakesort ... L  2; R  N; k  N ; faça para j  R até j  L , com passo j  j -1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para L  k + 1 para j  L até j  R , com passo j  j+1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para R  k - 1 enquanto ( L ≤ R ) ... 85 Introdução à Computação II – 5954006 8 45 12 43 56 19 67 95 a N = 8 1 2 3 4 5 6 7 8 L R k Término da 1ª “descida”. Término da primeira passagem (subida e descida de bolhas) ... L  2; R  N; k  N ; faça para j  R até j  L , com passo j  j -1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para L  k + 1 para j  L até j  R , com passo j  j+1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para R  k - 1 enquanto ( L ≤ R ) ... 5.3.2. Shakesort 86 Introdução à Computação II – 5954006 8 45 12 43 56 19 67 95 a N = 8 1 2 3 4 5 6 7 8 L R k Início da 2ª “subida”, pois L <= R j j -1 ... L  2; R  N; k  N ; faça para j  R até j  L , com passo j  j -1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para L  k + 1 para j  L até j  R , com passo j  j+1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para R  k - 1 enquanto ( L ≤ R ) ... 5.3.2. Shakesort 87 Introdução à Computação II – 5954006 8 45 12 43 56 19 67 95 a N = 8 1 2 3 4 5 6 7 8 L R k j j -1 ... L  2; R  N; k  N ; faça para j  R até j  L , com passo j  j -1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para L  k + 1 para j  L até j  R , com passo j  j+1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para R  k - 1 enquanto ( L ≤ R ) ... 5.3.2. Shakesort 88 Introdução à Computação II – 5954006 8 45 12 43 19 56 67 95 a N = 8 1 2 3 4 5 6 7 8 L R k j j -1 ... L  2; R  N; k  N ; faça para j  R até j  L , com passo j  j -1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para L  k + 1 para j  L até j  R , com passo j  j+1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para R  k - 1 enquanto ( L ≤ R ) ... 5.3.2. Shakesort 89 Introdução à Computação II – 5954006 8 45 12 43 19 56 67 95 a N = 8 1 2 3 4 5 6 7 8 L R k j j -1 ... L  2; R  N; k  N ; faça para j  R até j  L , com passo j  j -1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para L  k + 1 para j  L até j  R , com passo j  j+1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para R  k - 1 enquanto ( L ≤ R ) ... 5.3.2. Shakesort 90 Introdução à Computação II – 5954006 8 45 12 19 43 56 67 95 a N = 8 1 2 3 4 5 6 7 8 L R k j j -1 ... L  2; R  N; k  N ; faça para j  R até j  L , com passo j  j -1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para L  k + 1 para j  L até j  R , com passo j  j+1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para R  k - 1 enquanto ( L ≤ R ) ... 5.3.2. Shakesort 91 Introdução à Computação II – 5954006 8 45 12 19 43 56 67 95 a N = 8 1 2 3 4 5 6 7 8 L R k j j -1 ... L  2; R  N; k  N ; faça para j  R até j  L , com passo j  j -1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para L  k + 1 para j  L até j  R , com passo j  j+1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para R  k - 1 enquanto ( L ≤ R ) ... 5.3.2. Shakesort 92 Introdução à Computação II – 5954006 8 45 12 19 43 56 67 95 a N = 8 1 2 3 4 5 6 7 8 L R k j j -1 ... L  2; R  N; k  N ; faça para j  R até j  L , com passo j  j -1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para L  k + 1 para j  L até j  R , com passo j  j+1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para R  k - 1 enquanto ( L ≤ R ) ... 5.3.2. Shakesort 93 Introdução à Computação II – 5954006 8 12 45 19 43 56 67 95 a N = 8 1 2 3 4 5 6 7 8 L R k j j -1 ... L  2; R  N; k  N ; faça para j  R até j  L , com passo j  j -1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para L  k + 1 para j  L até j  R , com passo j  j+1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para R  k - 1 enquanto ( L ≤ R ) ... 5.3.2. Shakesort 94 Introdução à Computação II – 5954006 8 12 45 19 43 56 67 95 a N = 8 1 2 3 4 5 6 7 8 L R k Término da 2ª “subida” ... L  2; R  N; k  N ; faça para j  R até j  L , com passo j  j -1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para L  k + 1 para j  L até j  R , com passo j  j+1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para R  k - 1 enquanto ( L ≤ R ) ... 5.3.2. Shakesort 95 Introdução à Computação II – 5954006 8 12 45 19 43 56 67 95 a N = 8 1 2 3 4 5 6 7 8 L R k Início da 2ª “descida” j j -1 ... L  2; R  N; k  N ; faça para j  R até j  L , com passo j  j -1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para L  k + 1 para j  L até j  R , com passo j  j+1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para R  k - 1 enquanto ( L ≤ R ) ... 5.3.2. Shakesort 96 Introdução à Computação II – 5954006 8 12 19 45 43 56 67 95 a N = 8 1 2 3 4 5 6 7 8 L R k j j -1 ... L  2; R  N; k  N ; faça para j  R até j  L , com passo j  j -1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para L  k + 1 para j  L até j  R , com passo j  j+1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para R  k - 1 enquanto ( L ≤ R ) ... 5.3.2. Shakesort 97 Introdução à Computação II – 5954006 8 12 19 45 43 56 67 95 a N = 8 1 2 3 4 5 6 7 8 L R k j j -1 ... L  2; R  N; k  N ; faça para j  R até j  L , com passo j  j -1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para L  k + 1 para j  L até j  R , com passo j  j+1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para R  k - 1 enquanto ( L ≤ R ) ... 5.3.2. Shakesort 98 Introdução à Computação II – 5954006 8 12 19 43 45 56 67 95 a N = 8 1 2 3 4 5 6 7 8 L R k j j -1 ... L  2; R  N; k  N ; faça para j  R até j  L , com passo j  j -1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para L  k + 1 para j  L até j  R , com passo j  j+1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para R  k - 1 enquanto ( L ≤ R ) ... 5.3.2. Shakesort 99 Introdução à Computação II – 5954006 8 12 19 43 45 56 67 95 a N = 8 1 2 3 4 5 6 7 8 L R k j j -1 ... L  2; R  N; k  N ; faça para j  R até j  L , com passo j  j -1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para L  k + 1 para j  L até j  R , com passo j  j+1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para R  k - 1 enquanto ( L ≤ R ) ... 5.3.2. Shakesort 100 Introdução à Computação II – 5954006 8 12 19 43 45 56 67 95 a N = 8 1 2 3 4 5 6 7 8 L R k j j -1 ... L  2; R  N; k  N ; faça para j  R até j  L , com passo j  j -1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para L  k + 1 para j  L até j  R , com passo j  j+1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para R  k - 1 enquanto ( L ≤ R ) ... 5.3.2. Shakesort 101 Introdução à Computação II – 5954006 8 12 19 43 45 56 67 95 a N = 8 1 2 3 4 5 6 7 8 L R k Término da 2ª “descida”. ... L  2; R  N; k  N ; faça para j  R até j  L , com passo j  j -1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para L  k + 1 para j  L até j  R , com passo j  j+1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para R  k - 1 enquanto ( L ≤ R ) ... 5.3.2. Shakesort 102 Introdução à Computação II – 5954006 8 12 19 43 45 56 67 95 a N = 8 1 2 3 4 5 6 7 8 L R k Início da 3ª “subida”, pois L <= R ... L  2; R  N; k  N ; faça para j  R até j  L , com passo j  j -1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para L  k + 1 para j  L até j  R , com passo j  j+1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para R  k - 1 enquanto ( L ≤ R ) ... 5.3.2. Shakesort 103 Introdução à Computação II – 5954006 8 12 19 43 45 56 67 95 a N = 8 1 2 3 4 5 6 7 8 L R k j j -1 Término da 3ª “descida”. ... L  2; R  N; k  N ; faça para j  R até j  L , com passo j  j -1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para L  k + 1 para j  L até j  R , com passo j  j+1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para R  k - 1 enquanto ( L ≤ R ) ... 5.3.2. Shakesort 104 Introdução à Computação II – 5954006 8 12 19 43 45 56 67 95 a N = 8 1 2 3 4 5 6 7 8 L R k Início da 3ª “descida”. ... L  2; R  N; k  N ; faça para j  R até j  L , com passo j  j -1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para L  k + 1 para j  L até j  R , com passo j  j+1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para R  k - 1 enquanto ( L ≤ R ) ... 5.3.2. Shakesort 105 Introdução à Computação II – 5954006 8 12 19 43 45 56 67 95 a N = 8 1 2 3 4 5 6 7 8 L R k Término da 3ª “descida”. Note que o laço de descida não é executado nessa passagem. Como L > R, Vetor Ordenado ... L  2; R  N; k  N ; faça para j  R até j  L , com passo j  j -1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para L  k + 1 para j  L até j  R , com passo j  j+1 se ( a[ j - 1] > a[ j ] ) x  a [ j - 1 ] a [ j - 1 ]  a [ j ] a [ j ]  x k  j fim se fim para R  k - 1 enquanto ( L ≤ R ) ... 5.3.2. Shakesort 106 Introdução à Computação II – 5954006 • Análise ▪ Comparações ➢Mínimo: Cmin=N-1 – Quando está ordenado, faz apenas uma passagem de descida ➢Máximo: Cmax=(N2 -N)/2 – Quando está em ordem decrescente, o número de comparações é igual ao do BubbleSort ➢Médio: é proporcional a Cmed=(N2-N(K+ln(N)))/2, onde K é uma constante – A análise do Shakersort para o caso médio é complexa 5.3.2. Shakesort Fonte: Knuth, Donald E. (1973). «Sorting by Exchanging». Art of Computer Programming. 3. Sorting and Searching 1st ed. [S.l.]: Addison-Wesley. pp. 110–111. ISBN 0-201-03803-X 107 Introdução à Computação II – 5954006 • Análise ▪ Movimentações ➢Igual ao BubbleSort – As melhorias não afetam o número de movimentações: elas apenas reduzem o número de testes redundantes – Como a movimentação de dois elementos é uma operação mais onerosa do que a comparação de chaves, estas otimizações operam no algoritmo um ganho menor do que se poderia esperar 5.3.2. Shakesort 108 Introdução à Computação II – 5954006 • Análise 5.3.2. Shakesort Algoritmo Cmín Cméd Cmáx Mmín Mméd Mmáx Inserção Direta O(N) O(N2) O(N2) O(N) O(N2) O(N2) Inserção Binária O(N*log2N) O(N*log2N) O(N*log2N) O(N) O(N2) O(N2) Seleção Direta O(N2) O(N2) O(N2) O(N) O(N) O(N) Bubblesort O(N2) O(N2) O(N2) O(1) O(N2) O(N2) Shakersort O(N) O(N2) O(N2) O(1) O(N2) O(N2) 109 Introdução à Computação II – 5954006 5.3.2. Shakesort • Exercício 5.3.2. Utilizando ordenação por shakesort, obtenha o número de comparações e movimentações em cada passo para os seguintes vetores ▪ [ 45 56 12 43 95 19 8 67 ] ▪ [ 8 12 19 43 45 56 67 95 ] ▪ [ 95 67 56 45 43 19 12 8 ] ▪ [ 19 12 8 45 43 56 67 95 ] 110 Introdução à Computação II – 5954006 L R Ci Mi 45 56 12 43 95 19 8 67 3 7 13 30 8 45 12 43 56 19 67 95 4 4 9 15 8 12 19 43 45 56 67 95 6 4 1 0 8 12 19 43 45 56 67 95 23 45 L R Ci Mi 8 12 19 43 45 56 67 95 9 7 7 0 8 12 19 43 45 56 67 95 7 0 L R Ci Mi 95 67 56 45 43 19 12 8 3 7 13 39 8 67 56 45 43 19 12 95 4 6 9 27 8 12 56 45 43 19 67 95 5 5 5 15 8 12 19 45 43 56 67 95 6 4 1 3 8 12 19 43 45 56 67 95 28 84 L R Ci Mi 19 12 8 45 43 56 67 95 3 2 13 12 8 12 19 43 45 56 67 95 13 12 Exercício 5.3.2. Solução 5.3.2. Shakesort 111 Introdução à Computação II – 5954006 Comparações 0 5 10 15 20 25 30 35 40 Inserção Direta Inserção Binária Seleção Bublesort Shakesort Comparações 45,56,12,43,95,19,8,67 8,12,19,43,45,56,67,95 95,67,56,45,43,19,12,8 19,12,8,45,43,56,67,95 112 Introdução à Computação II – 5954006 Movimentações 0 10 20 30 40 50 60 70 80 90 Inserção Direta Inserção Binária Seleção Bublesort Shakesort Movimentações 45,56,12,43,95,19,8,67 8,12,19,43,45,56,67,95 95,67,56,45,43,19,12,8 19,12,8,45,43,56,67,95 113 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