Slide - Algoritmos de Ordenaçã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. Algoritmos de Ordenação • Ordenação é o processo de rearranjo de um conjunto de registros de acordo com um dado critério ▪ Exemplo: elementos de um vetor ordenados em ordem crescente • O objetivo da ordenação é facilitar a localização de objetos pertencentes ao conjunto • É uma atividade bastante utilizada na elaboração de algoritmos mais complexos • Exemplos ▪ listas telefônicas ▪ índices ▪ dicionários ▪ contas bancárias ▪ itens em um almoxarifado 4 Introdução à Computação II – 5954006 • Notação ▪ Assumindo-se que os elementos a serem ordenados estão em um vetor a com N elementos, ou seja: a = [ a(1) a(2) ... a(N) ] ▪ a ordenação consistirá em permutar tais elementos, levando ao vetor ap = [ a(k1) a(k2) ... a(kN) ] ▪ de forma tal que, considerando a função f de ordenação, seja satisfeita a seguinte relação: f ( a(k1) ) ≤ f ( a(k2) ) ≤ ... ≤ f ( a(kN) ) 5. Algoritmos de Ordenação 5 Introdução à Computação II – 5954006 • Estabilidade x Instabilidade ▪ Um método de ordenação é denominado estável se ➢a ordem relativa dos elementos que exibam a mesma chave permanecer inalterada ao longo de todo o processo de ordenação ▪ Caso contrário, ele é denominado instável ▪ Em geral, a estabilidade da ordenação é desejável ➢especialmente quando os elementos já estiverem ordenados em relação a uma ou mais chaves secundárias 5. Algoritmos de Ordenação 6 Introdução à Computação II – 5954006 • Os métodos de ordenação são classificados em dois grandes grupos ▪ Ordenação interna ➢o conjunto de objetos cabe todo na memória principal ▪ Ordenação externa ➢o conjunto de objetos é muito grande para a memória principal e, portanto, é armazenado na memória secundária 5. Algoritmos de Ordenação 7 Introdução à Computação II – 5954006 • Notação ▪ O valor da função de ordenação para um dado objeto é armazenada como um componente explícito (campo) deste objeto ▪ Seu valor é denominado chave ▪ Em C, estruturas (struct) são particularmente interessantes para representar tais objetos ... typedef struct { tipo chave; // chave ... // demais informações } item ; ... item a[N]; ... 5. Algoritmos de Ordenação 8 Introdução à Computação II – 5954006 • Por simplicidade, considere que ▪ O vetor de registros é um vetor de inteiros no qual os elementos são as chaves ➢ ou seja, o tipo item é inteiro ▪ N é uma constante que indica o número de elementos do vetor • Assim, objetivo da ordenação se resume a ordenar os elementos (chaves) do vetor dado de acordo com o critério pré-estabelecido ▪ Nos métodos aqui apresentados, será considerado que desejamos ordenar os elementos do vetor de forma crescente 5. Algoritmos de Ordenação 9 Introdução à Computação II – 5954006 • Exemplos de métodos de ordenação 5.1. Ordenação por Inserção 5.1.1. Inserção Direta 5.1.2. Inserção Binária 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 5. Algoritmos de Ordenação 10 Introdução à Computação II – 5954006 5.1. Ordenação por Inserção • Um dos métodos mais populares ▪ Analogia com a ordenação de cartas executada por um jogador • Utiliza duas seqüências ▪ Seqüência fonte ▪ Seqüência destino • Dois Tipos ▪ Ordenação direta ▪ Ordenação binária 11 Introdução à Computação II – 5954006 5.1.1. Inserção Direta • Os elementos são conceitualmente divididos em ▪ uma seqüência destino ➢a[1], a[2], ...,a[i-1] ▪ uma seqüência fonte ➢a[i], a[i+1], ... a[N] • Em cada passo, iniciando-se com i = 2 e incrementando-se i de uma unidade, o i-ésimo elemento da seqüência vai sendo retirado da seqüência fonte e inserido na posição apropriada (ordenada) da seqüência destino 12 Introdução à Computação II – 5954006 ... para i  2 até i  N x  a [ i ] inserir x no local adequado da seqüência a[1] ... a[i] fim para ... 5.1.1. Inserção Direta • Algoritmo padrão 13 Introdução à Computação II – 5954006 • No processo de procurar o local apropriado para o elemento x, é conveniente utilizar, de modo alternado, operações de ▪ comparação, ➢examinar x e compará-lo com o próximo elemento a[j] ▪ movimentação ➢efetuar a inserção de x ou a movimentação do elemento a[j] para a direita, prosseguido-se, em seguida, para a esquerda 5.1.1. Inserção Direta 14 Introdução à Computação II – 5954006 • Note que existem duas condições distintas que causam o término deste processo de análise: ▪ Um elemento a[j] é encontrado com uma chave de valor menor do que o da chave do elemento x ▪ A extremidade esquerda do vetor a é atingida. • O uso de um loop com duas condições de término é equivalente ao caso da técnica da sentinela vista nas aulas sobre busca em vetores • Observe que esta técnica é facilmente aplicada neste caso colocando-se uma sentinela com valor de x em a[0] 5.1.1. Inserção Direta 15 Introdução à Computação II – 5954006 0 1 2 3 4 5 6 7 8 45 56 12 43 95 19 8 67 a N = 8 i 56 j j -1 5.1.1. Inserção Direta ... para i  2 até i  N x  a [ i ] a [ 0 ]  x j  i enquanto x < a[ j-1] a[ j ]  a[ j-1] j  j - 1 fim enquanto a [ j ]  x fim para ... Exemplo 5.1.1. 16 Introdução à Computação II – 5954006 0 1 2 3 4 5 6 7 8 45 56 12 43 95 19 8 67 a N = 8 i 12 j j -1 ... para i  2 até i  N x  a [ i ] a [ 0 ]  x j  i enquanto x < a[ j-1] a[ j ]  a[ j-1] j  j - 1 fim enquanto a [ j ]  x fim para ... Exemplo 5.1.1. 5.1.1. Inserção Direta 17 Introdução à Computação II – 5954006 0 1 2 3 4 5 6 7 8 45 56 56 43 95 19 8 67 a N = 8 i 12 j j -1 ... para i  2 até i  N x  a [ i ] a [ 0 ]  x j  i enquanto x < a[ j-1] a[ j ]  a[ j-1] j  j - 1 fim enquanto a [ j ]  x fim para ... Exemplo 5.1.1. 5.1.1. Inserção Direta 18 Introdução à Computação II – 5954006 0 1 2 3 4 5 6 7 8 45 45 56 43 95 19 8 67 a N = 8 i 12 j j -1 ... para i  2 até i  N x  a [ i ] a [ 0 ]  x j  i enquanto x < a[ j-1] a[ j ]  a[ j-1] j  j - 1 fim enquanto a [ j ]  x fim para ... Exemplo 5.1.1. 5.1.1. Inserção Direta 19 Introdução à Computação II – 5954006 0 1 2 3 4 5 6 7 8 12 45 56 43 95 19 8 67 a N = 8 i 12 j j -1 5.1.1. Inserção Direta ... para i  2 até i  N x  a [ i ] a [ 0 ]  x j  i enquanto x < a[ j-1] a[ j ]  a[ j-1] j  j - 1 fim enquanto a [ j ]  x fim para ... Exemplo 5.1.1. 20 Introdução à Computação II – 5954006 0 1 2 3 4 5 6 7 8 12 45 56 43 95 19 8 67 a N = 8 i 43 j j -1 ... para i  2 até i  N x  a [ i ] a [ 0 ]  x j  i enquanto x < a[ j-1] a[ j ]  a[ j-1] j  j - 1 fim enquanto a [ j ]  x fim para ... Exemplo 5.1.1. 5.1.1. Inserção Direta 21 Introdução à Computação II – 5954006 0 1 2 3 4 5 6 7 8 12 45 56 56 95 19 8 67 a N = 8 i 43 j j -1 ... para i  2 até i  N x  a [ i ] a [ 0 ]  x j  i enquanto x < a[ j-1] a[ j ]  a[ j-1] j  j - 1 fim enquanto a [ j ]  x fim para ... Exemplo 5.1.1. 5.1.1. Inserção Direta 22 Introdução à Computação II – 5954006 0 1 2 3 4 5 6 7 8 12 45 45 56 95 19 8 67 a N = 8 i 43 j j -1 ... para i  2 até i  N x  a [ i ] a [ 0 ]  x j  i enquanto x < a[ j-1] a[ j ]  a[ j-1] j  j - 1 fim enquanto a [ j ]  x fim para ... Exemplo 5.1.1. 5.1.1. Inserção Direta 23 Introdução à Computação II – 5954006 0 1 2 3 4 5 6 7 8 12 43 45 56 95 19 8 67 a N = 8 i 43 j j -1 ... para i  2 até i  N x  a [ i ] a [ 0 ]  x j  i enquanto x < a[ j-1] a[ j ]  a[ j-1] j  j - 1 fim enquanto a [ j ]  x fim para ... Exemplo 5.1.1. 5.1.1. Inserção Direta 24 Introdução à Computação II – 5954006 0 1 2 3 4 5 6 7 8 12 43 45 56 95 19 8 67 a N = 8 i 95 j j -1 ... para i  2 até i  N x  a [ i ] a [ 0 ]  x j  i enquanto x < a[ j-1] a[ j ]  a[ j-1] j  j - 1 fim enquanto a [ j ]  x fim para ... Exemplo 5.1.1. 5.1.1. Inserção Direta 25 Introdução à Computação II – 5954006 0 1 2 3 4 5 6 7 8 12 43 45 56 95 19 8 67 a N = 8 i 19 j j -1 ... para i  2 até i  N x  a [ i ] a [ 0 ]  x j  i enquanto x < a[ j-1] a[ j ]  a[ j-1] j  j - 1 fim enquanto a [ j ]  x fim para ... Exemplo 5.1.1. 5.1.1. Inserção Direta 26 Introdução à Computação II – 5954006 0 1 2 3 4 5 6 7 8 12 43 45 56 95 95 8 67 a N = 8 i 19 j j -1 ... para i  2 até i  N x  a [ i ] a [ 0 ]  x j  i enquanto x < a[ j-1] a[ j ]  a[ j-1] j  j - 1 fim enquanto a [ j ]  x fim para ... Exemplo 5.1.1. 5.1.1. Inserção Direta 27 Introdução à Computação II – 5954006 0 1 2 3 4 5 6 7 8 12 43 45 56 56 95 8 67 a N = 8 i 19 j j -1 ... para i  2 até i  N x  a [ i ] a [ 0 ]  x j  i enquanto x < a[ j-1] a[ j ]  a[ j-1] j  j - 1 fim enquanto a [ j ]  x fim para ... Exemplo 5.1.1. 5.1.1. Inserção Direta 28 Introdução à Computação II – 5954006 0 1 2 3 4 5 6 7 8 12 43 45 45 56 95 8 67 a N = 8 i 19 j j -1 ... para i  2 até i  N x  a [ i ] a [ 0 ]  x j  i enquanto x < a[ j-1] a[ j ]  a[ j-1] j  j - 1 fim enquanto a [ j ]  x fim para ... Exemplo 5.1.1. 5.1.1. Inserção Direta 29 Introdução à Computação II – 5954006 0 1 2 3 4 5 6 7 8 12 43 43 45 56 95 8 67 a N = 8 i 19 j j -1 ... para i  2 até i  N x  a [ i ] a [ 0 ]  x j  i enquanto x < a[ j-1] a[ j ]  a[ j-1] j  j - 1 fim enquanto a [ j ]  x fim para ... Exemplo 5.1.1. 5.1.1. Inserção Direta 30 Introdução à Computação II – 5954006 0 1 2 3 4 5 6 7 8 12 19 43 45 56 95 8 67 a N = 8 i 19 j j -1 ... para i  2 até i  N x  a [ i ] a [ 0 ]  x j  i enquanto x < a[ j-1] a[ j ]  a[ j-1] j  j - 1 fim enquanto a [ j ]  x fim para ... Exemplo 5.1.1. 5.1.1. Inserção Direta 31 Introdução à Computação II – 5954006 0 1 2 3 4 5 6 7 8 12 19 43 45 56 95 8 67 a N = 8 i 8 j j -1 ... para i  2 até i  N x  a [ i ] a [ 0 ]  x j  i enquanto x < a[ j-1] a[ j ]  a[ j-1] j  j - 1 fim enquanto a [ j ]  x fim para ... Exemplo 5.1.1. 5.1.1. Inserção Direta 32 Introdução à Computação II – 5954006 0 1 2 3 4 5 6 7 8 12 19 43 45 56 95 95 67 a N = 8 i 8 j j -1 ... para i  2 até i  N x  a [ i ] a [ 0 ]  x j  i enquanto x < a[ j-1] a[ j ]  a[ j-1] j  j - 1 fim enquanto a [ j ]  x fim para ... Exemplo 5.1.1. 5.1.1. Inserção Direta 33 Introdução à Computação II – 5954006 0 1 2 3 4 5 6 7 8 12 19 43 45 56 56 95 67 a N = 8 i 8 j j -1 ... para i  2 até i  N x  a [ i ] a [ 0 ]  x j  i enquanto x < a[ j-1] a[ j ]  a[ j-1] j  j - 1 fim enquanto a [ j ]  x fim para ... Exemplo 5.1.1. 5.1.1. Inserção Direta 34 Introdução à Computação II – 5954006 0 1 2 3 4 5 6 7 8 12 19 43 45 45 56 95 67 a N = 8 i 8 j j -1 ... para i  2 até i  N x  a [ i ] a [ 0 ]  x j  i enquanto x < a[ j-1] a[ j ]  a[ j-1] j  j - 1 fim enquanto a [ j ]  x fim para ... Exemplo 5.1.1. 5.1.1. Inserção Direta 35 Introdução à Computação II – 5954006 0 1 2 3 4 5 6 7 8 12 19 43 43 45 56 95 67 a N = 8 i 8 j j -1 ... para i  2 até i  N x  a [ i ] a [ 0 ]  x j  i enquanto x < a[ j-1] a[ j ]  a[ j-1] j  j - 1 fim enquanto a [ j ]  x fim para ... Exemplo 5.1.1. 5.1.1. Inserção Direta 36 Introdução à Computação II – 5954006 0 1 2 3 4 5 6 7 8 12 19 19 43 45 56 95 67 a N = 8 i 8 j j -1 ... para i  2 até i  N x  a [ i ] a [ 0 ]  x j  i enquanto x < a[ j-1] a[ j ]  a[ j-1] j  j - 1 fim enquanto a [ j ]  x fim para ... Exemplo 5.1.1. 5.1.1. Inserção Direta 37 Introdução à Computação II – 5954006 0 1 2 3 4 5 6 7 8 12 12 19 43 45 56 95 67 a N = 8 i 8 j j -1 ... para i  2 até i  N x  a [ i ] a [ 0 ]  x j  i enquanto x < a[ j-1] a[ j ]  a[ j-1] j  j - 1 fim enquanto a [ j ]  x fim para ... Exemplo 5.1.1. 5.1.1. Inserção Direta 38 Introdução à Computação II – 5954006 0 1 2 3 4 5 6 7 8 8 12 19 43 45 56 95 67 a N = 8 i 8 j j -1 ... para i  2 até i  N x  a [ i ] a [ 0 ]  x j  i enquanto x < a[ j-1] a[ j ]  a[ j-1] j  j - 1 fim enquanto a [ j ]  x fim para ... Exemplo 5.1.1. 5.1.1. Inserção Direta 39 Introdução à Computação II – 5954006 0 1 2 3 4 5 6 7 8 8 12 19 43 45 56 95 67 a N = 8 i 67 j j -1 ... para i  2 até i  N x  a [ i ] a [ 0 ]  x j  i enquanto x < a[ j-1] a[ j ]  a[ j-1] j  j - 1 fim enquanto a [ j ]  x fim para ... Exemplo 5.1.1. 5.1.1. Inserção Direta 40 Introdução à Computação II – 5954006 0 1 2 3 4 5 6 7 8 8 12 19 43 45 56 95 95 a N = 8 i 67 j j -1 ... para i  2 até i  N x  a [ i ] a [ 0 ]  x j  i enquanto x < a[ j-1] a[ j ]  a[ j-1] j  j - 1 fim enquanto a [ j ]  x fim para ... Exemplo 5.1.1. 5.1.1. Inserção Direta 41 Introdução à Computação II – 5954006 0 1 2 3 4 5 6 7 8 8 12 19 43 45 56 67 95 a N = 8 i 67 j j -1 ... para i  2 até i  N x  a [ i ] a [ 0 ]  x j  i enquanto x < a[ j-1] a[ j ]  a[ j-1] j  j - 1 fim enquanto a [ j ]  x fim para ... Exemplo 5.1.1. 5.1.1. Inserção Direta 42 Introdução à Computação II – 5954006 0 1 2 3 4 5 6 7 8 8 12 19 43 45 56 67 95 a N = 8 67 Vetor ordenado! ... para i  2 até i  N x  a [ i ] a [ 0 ]  x j  i enquanto x < a[ j-1] a[ j ]  a[ j-1] j  j - 1 fim enquanto a [ j ]  x fim para ... Exemplo 5.1.1. 5.1.1. Inserção Direta 43 Introdução à Computação II – 5954006 Vetor inicial 45 56 12 43 95 19 8 67 i = 2 45 56 12 43 95 19 8 67 i = 3 12 45 56 43 95 19 8 67 i = 4 12 43 45 56 95 19 8 67 i = 5 12 43 45 56 95 19 8 67 i = 6 12 19 43 45 56 95 8 67 i = 7 8 12 19 43 45 56 95 67 i = 8 8 12 19 43 45 56 67 95 5.1.1. Inserção Direta Exemplo 5.1.1. 44 Introdução à Computação II – 5954006 https://www.youtube.com/watch?v=ROalU379l3U Insert-sort with Romanian folk dance 5.1.1. Inserção Direta 45 Introdução à Computação II – 5954006 • Análise ▪ O método é estável ▪ Análise Assintótica do número de comparações entre chaves e movimentações de registros ➢ O número Ci de comparações das chaves no i-ésimo passo é de, – no máximo: i – no mínimo: 1 – em média, admitindo-se que todas as N chaves sejam igualmente prováveis, ➢ O número Mi de movimentos é (Ci -1+3) – o número mínimo ocorre se os elementos já estiverem, inicialmente, ordenados – o pior caso ocorre se eles estiverem, inicialmente, em ordem reversa 5.1.1. Inserção Direta Ver análise na lousa 2 1 1 1 = +  = i j i i j 46 Introdução à Computação II – 5954006 ) ( 1 1 2 mín O N N C N i − = = = = ) ( )1 3( 2 1 2 mín O N N M N i = − = + =  = ) ( 4 4 3 2 1 2 2 2 méd O N N N i C N i = − + = + =  = ) ( 4 12 11 2 2 1 2 2 2 méd O N N N i M N i = − + = + + = = ) ( 2 2 2 2 2 máx O N N N i C N i = − + = =  = ) ( 2 6 5 2 2 2 2 máx O N N N i M N i = − + = + =  = 5.1.1. Inserção Direta ... para i  2 até i  N x  a [ i ] a [ 0 ]  x j  i enquanto x < a[ j-1] a[ j ]  a[ j-1] j  j - 1 fim enquanto a [ j ]  x fim para ... 47 Introdução à Computação II – 5954006 Exercício 5.1.1. Utilizando o algoritmo de inserção direta, 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.1.1. Inserção Direta 48 Introdução à Computação II – 5954006 i Ci Mi 8 12 19 43 45 56 67 95 2 1 3 8 12 19 43 45 56 67 95 3 1 3 8 12 19 43 45 56 67 95 4 1 3 8 12 19 43 45 56 67 95 5 1 3 8 12 19 43 45 56 67 95 6 1 3 8 12 19 43 45 56 67 95 7 1 3 8 12 19 43 45 56 67 95 8 1 3 8 12 19 43 45 56 67 95 7 21 i Ci Mi 45 56 12 43 95 19 8 67 2 1 3 45 56 12 43 95 19 8 67 3 3 5 12 45 56 43 95 19 8 67 4 3 5 12 43 45 56 95 19 8 67 5 1 3 12 43 45 56 95 19 8 67 6 5 7 12 19 43 45 56 95 8 67 7 7 9 8 12 19 43 45 56 95 67 8 2 4 8 12 19 43 45 56 67 95 22 36 i Ci Mi 95 67 56 45 43 19 12 8 2 2 4 67 95 56 45 43 19 12 8 3 3 5 56 67 95 45 43 19 12 8 4 4 6 45 56 67 95 43 19 12 8 5 5 7 43 45 56 67 95 19 12 8 6 6 8 19 43 45 56 67 95 12 8 7 7 9 12 19 43 45 56 67 95 8 8 8 10 8 12 19 43 45 56 67 95 35 49 i Ci Mi 19 12 8 45 43 56 67 95 2 2 4 12 19 8 45 43 56 67 95 3 3 5 8 12 19 45 43 56 67 95 4 1 3 8 12 19 45 43 56 67 95 5 2 4 8 12 19 43 45 56 67 95 6 1 3 8 12 19 43 45 56 67 95 7 1 3 8 12 19 43 45 56 67 95 8 1 3 8 12 19 43 45 56 67 95 11 25 5.1.1. Inserção Direta Exercício 5.1.1. Solução 49 Introdução à Computação II – 5954006 • O algoritmo de inserção direta pode ser aperfeiçoado observando-se que a seqüência destino a[1], a[2], ..., a[i-1], na qual deve ser inserido o elemento x, já está ordenada • Assim, pode-se utilizar um método mais rápido para determinar o ponto correto de inserção • A escolha óbvia é o método da busca binária, que divide a seqüência destino no seu ponto central, continuando a divisão até encontrar o ponto correto de inserção 5.1.2. Inserção Binária 50 Introdução à Computação II – 5954006 1 2 3 4 5 6 7 45 56 12 43 95 19 8 a N = 7 i L R m ... para i  2 até i  N x  a [ i ] L  1 R  i enquanto ( L < R ) m  floor ( ( L + R ) / 2) se (a[m] ≤ x ) L  m + 1 senão R  m fim se fim enquanto j  i enquanto ( j > R ) a[ j ]  a[ j-1] j  j – 1 fim enquanto a [ R ]  x fim para ... 5.1.2. Inserção Binária x = 56 Exemplo 5.1.2. 51 Introdução à Computação II – 5954006 5.1.2. Inserção Binária 1 2 3 4 5 6 7 45 56 12 43 95 19 8 a N = 7 i L R m ... para i  2 até i  N x  a [ i ] L  1 R  i enquanto ( L < R ) m  floor ( ( L + R ) / 2) se (a[m] ≤ x ) L  m + 1 senão R  m fim se fim enquanto j  i enquanto ( j > R ) a[ j ]  a[ j-1] j  j – 1 fim enquanto a [ R ]  x fim para ... x = 56 52 Introdução à Computação II – 5954006 1 2 3 4 5 6 7 45 56 12 43 95 19 8 a N = 7 i L R m ... para i  2 até i  N x  a [ i ] L  1 R  i enquanto ( L < R ) m  floor ( ( L + R ) / 2) se (a[m] ≤ x ) L  m + 1 senão R  m fim se fim enquanto j  i enquanto ( j > R ) a[ j ]  a[ j-1] j  j – 1 fim enquanto a [ R ]  x fim para ... x = 12 5.1.2. Inserção Binária 53 Introdução à Computação II – 5954006 1 2 3 4 5 6 7 45 56 12 43 95 19 8 a N = 7 i L R m ... para i  2 até i  N x  a [ i ] L  1 R  i enquanto ( L < R ) m  floor ( ( L + R ) / 2) se (a[m] ≤ x ) L  m + 1 senão R  m fim se fim enquanto j  i enquanto ( j > R ) a[ j ]  a[ j-1] j  j – 1 fim enquanto a [ R ]  x fim para ... x = 12 5.1.2. Inserção Binária 54 Introdução à Computação II – 5954006 1 2 3 4 5 6 7 45 56 12 43 95 19 8 a N = 7 i L R m ... para i  2 até i  N x  a [ i ] L  1 R  i enquanto ( L < R ) m  floor ( ( L + R ) / 2) se (a[m] ≤ x ) L  m + 1 senão R  m fim se fim enquanto j  i enquanto ( j > R ) a[ j ]  a[ j-1] j  j – 1 fim enquanto a [ R ]  x fim para ... j x = 12 5.1.2. Inserção Binária 55 Introdução à Computação II – 5954006 1 2 3 4 5 6 7 45 56 56 43 95 19 8 a N = 7 i L R m j ... para i  2 até i  N x  a [ i ] L  1 R  i enquanto ( L < R ) m  floor ( ( L + R ) / 2) se (a[m] ≤ x ) L  m + 1 senão R  m fim se fim enquanto j  i enquanto ( j > R ) a[ j ]  a[ j-1] j  j – 1 fim enquanto a [ R ]  x fim para ... x = 12 5.1.2. Inserção Binária 56 Introdução à Computação II – 5954006 1 2 3 4 5 6 7 45 45 56 43 95 19 8 a N = 7 i L R m j ... para i  2 até i  N x  a [ i ] L  1 R  i enquanto ( L < R ) m  floor ( ( L + R ) / 2) se (a[m] ≤ x ) L  m + 1 senão R  m fim se fim enquanto j  i enquanto ( j > R ) a[ j ]  a[ j-1] j  j – 1 fim enquanto a [ R ]  x fim para ... x = 12 5.1.2. Inserção Binária 57 Introdução à Computação II – 5954006 1 2 3 4 5 6 7 12 45 56 43 95 19 8 a N = 7 i L R m x = 12 ... para i  2 até i  N x  a [ i ] L  1 R  i enquanto ( L < R ) m  floor ( ( L + R ) / 2) se (a[m] ≤ x ) L  m + 1 senão R  m fim se fim enquanto j  i enquanto ( j > R ) a[ j ]  a[ j-1] j  j – 1 fim enquanto a [ R ]  x fim para ... 5.1.2. Inserção Binária 58 Introdução à Computação II – 5954006 1 2 3 4 5 6 7 12 45 56 43 95 19 8 a N = 7 i L R m x = 43 ... para i  2 até i  N x  a [ i ] L  1 R  i enquanto ( L < R ) m  floor ( ( L + R ) / 2) se (a[m] ≤ x ) L  m + 1 senão R  m fim se fim enquanto j  i enquanto ( j > R ) a[ j ]  a[ j-1] j  j – 1 fim enquanto a [ R ]  x fim para ... 5.1.2. Inserção Binária 59 Introdução à Computação II – 5954006 1 2 3 4 5 6 7 12 45 56 43 95 19 8 a N = 7 i L R m x = 43 ... para i  2 até i  N x  a [ i ] L  1 R  i enquanto ( L < R ) m  floor ( ( L + R ) / 2) se (a[m] ≤ x ) L  m + 1 senão R  m fim se fim enquanto j  i enquanto ( j > R ) a[ j ]  a[ j-1] j  j – 1 fim enquanto a [ R ]  x fim para ... 5.1.2. Inserção Binária 60 Introdução à Computação II – 5954006 1 2 3 4 5 6 7 12 45 56 43 95 19 8 a N = 7 i L R m j ... para i  2 até i  N x  a [ i ] L  1 R  i enquanto ( L < R ) m  floor ( ( L + R ) / 2) se (a[m] ≤ x ) L  m + 1 senão R  m fim se fim enquanto j  i enquanto ( j > R ) a[ j ]  a[ j-1] j  j – 1 fim enquanto a [ R ]  x fim para ... x = 43 5.1.2. Inserção Binária 61 Introdução à Computação II – 5954006 1 2 3 4 5 6 7 12 45 56 56 95 19 8 a N = 7 i L R m j ... para i  2 até i  N x  a [ i ] L  1 R  i enquanto ( L < R ) m  floor ( ( L + R ) / 2) se (a[m] ≤ x ) L  m + 1 senão R  m fim se fim enquanto j  i enquanto ( j > R ) a[ j ]  a[ j-1] j  j – 1 fim enquanto a [ R ]  x fim para ... x = 43 5.1.2. Inserção Binária 62 Introdução à Computação II – 5954006 1 2 3 4 5 6 7 12 45 45 56 95 19 8 a N = 7 i L R m x = 43 ... para i  2 até i  N x  a [ i ] L  1 R  i enquanto ( L < R ) m  floor ( ( L + R ) / 2) se (a[m] ≤ x ) L  m + 1 senão R  m fim se fim enquanto j  i enquanto ( j > R ) a[ j ]  a[ j-1] j  j – 1 fim enquanto a [ R ]  x fim para ... 5.1.2. Inserção Binária 63 Introdução à Computação II – 5954006 1 2 3 4 5 6 7 12 43 45 56 95 19 8 a N = 7 i L R m 5.1.2. Inserção Binária x = 43 ... para i  2 até i  N x  a [ i ] L  1 R  i enquanto ( L < R ) m  floor ( ( L + R ) / 2) se (a[m] ≤ x ) L  m + 1 senão R  m fim se fim enquanto j  i enquanto ( j > R ) a[ j ]  a[ j-1] j  j – 1 fim enquanto a [ R ]  x fim para ... 64 Introdução à Computação II – 5954006 1 2 3 4 5 6 7 12 43 45 56 95 19 8 a N = 7 i L R m 5.1.2. Inserção Binária ... para i  2 até i  N x  a [ i ] L  1 R  i enquanto ( L < R ) m  floor ( ( L + R ) / 2) se (a[m] ≤ x ) L  m + 1 senão R  m fim se fim enquanto j  i enquanto ( j > R ) a[ j ]  a[ j-1] j  j – 1 fim enquanto a [ R ]  x fim para ... x = 95 65 Introdução à Computação II – 5954006 1 2 3 4 5 6 7 12 43 45 56 95 19 8 a N = 7 i L R m ... para i  2 até i  N x  a [ i ] L  1 R  i enquanto ( L < R ) m  floor ( ( L + R ) / 2) se (a[m] ≤ x ) L  m + 1 senão R  m fim se fim enquanto j  i enquanto ( j > R ) a[ j ]  a[ j-1] j  j – 1 fim enquanto a [ R ]  x fim para ... x = 95 5.1.2. Inserção Binária 66 Introdução à Computação II – 5954006 1 2 3 4 5 6 7 12 43 45 56 95 19 8 a N = 7 i L R m j ... para i  2 até i  N x  a [ i ] L  1 R  i enquanto ( L < R ) m  floor ( ( L + R ) / 2) se (a[m] ≤ x ) L  m + 1 senão R  m fim se fim enquanto j  i enquanto ( j > R ) a[ j ]  a[ j-1] j  j – 1 fim enquanto a [ R ]  x fim para ... x = 95 5.1.2. Inserção Binária 67 Introdução à Computação II – 5954006 1 2 3 4 5 6 7 12 43 45 56 95 19 8 a N = 7 i L R m ... para i  2 até i  N x  a [ i ] L  1 R  i enquanto ( L < R ) m  floor ( ( L + R ) / 2) se (a[m] ≤ x ) L  m + 1 senão R  m fim se fim enquanto j  i enquanto ( j > R ) a[ j ]  a[ j-1] j  j – 1 fim enquanto a [ R ]  x fim para ... x = 95 5.1.2. Inserção Binária 68 Introdução à Computação II – 5954006 1 2 3 4 5 6 7 12 43 45 56 95 19 8 a N = 7 i L R m ... para i  2 até i  N x  a [ i ] L  1 R  i enquanto ( L < R ) m  floor ( ( L + R ) / 2) se (a[m] ≤ x ) L  m + 1 senão R  m fim se fim enquanto j  i enquanto ( j > R ) a[ j ]  a[ j-1] j  j – 1 fim enquanto a [ R ]  x fim para ... x = 19 5.1.2. Inserção Binária 69 Introdução à Computação II – 5954006 1 2 3 4 5 6 7 12 43 45 56 95 19 8 a N = 7 i L R m ... para i  2 até i  N x  a [ i ] L  1 R  i enquanto ( L < R ) m  floor ( ( L + R ) / 2) se (a[m] ≤ x ) L  m + 1 senão R  m fim se fim enquanto j  i enquanto ( j > R ) a[ j ]  a[ j-1] j  j – 1 fim enquanto a [ R ]  x fim para ... x = 19 5.1.2. Inserção Binária 70 Introdução à Computação II – 5954006 1 2 3 4 5 6 7 12 43 45 56 95 19 8 a N = 7 i L R m ... para i  2 até i  N x  a [ i ] L  1 R  i enquanto ( L < R ) m  floor ( ( L + R ) / 2) se (a[m] ≤ x ) L  m + 1 senão R  m fim se fim enquanto j  i enquanto ( j > R ) a[ j ]  a[ j-1] j  j – 1 fim enquanto a [ R ]  x fim para ... x = 19 5.1.2. Inserção Binária 71 Introdução à Computação II – 5954006 1 2 3 4 5 6 7 12 43 45 56 95 19 8 a N = 7 i L R m j ... para i  2 até i  N x  a [ i ] L  1 R  i enquanto ( L < R ) m  floor ( ( L + R ) / 2) se (a[m] ≤ x ) L  m + 1 senão R  m fim se fim enquanto j  i enquanto ( j > R ) a[ j ]  a[ j-1] j  j – 1 fim enquanto a [ R ]  x fim para ... x = 19 5.1.2. Inserção Binária 72 Introdução à Computação II – 5954006 1 2 3 4 5 6 7 12 43 45 56 95 95 8 a N = 7 i L R m j ... para i  2 até i  N x  a [ i ] L  1 R  i enquanto ( L < R ) m  floor ( ( L + R ) / 2) se (a[m] ≤ x ) L  m + 1 senão R  m fim se fim enquanto j  i enquanto ( j > R ) a[ j ]  a[ j-1] j  j – 1 fim enquanto a [ R ]  x fim para ... x = 19 5.1.2. Inserção Binária 73 Introdução à Computação II – 5954006 1 2 3 4 5 6 7 12 43 45 56 56 95 8 a N = 8 i L R m j ... para i  2 até i  N x  a [ i ] L  1 R  i enquanto ( L < R ) m  floor ( ( L + R ) / 2) se (a[m] ≤ x ) L  m + 1 senão R  m fim se fim enquanto j  i enquanto ( j > R ) a[ j ]  a[ j-1] j  j – 1 fim enquanto a [ R ]  x fim para ... x = 19 5.1.2. Inserção Binária 74 Introdução à Computação II – 5954006 1 2 3 4 5 6 7 12 43 45 45 56 95 8 a N = 7 i L R m j ... para i  2 até i  N x  a [ i ] L  1 R  i enquanto ( L < R ) m  floor ( ( L + R ) / 2) se (a[m] ≤ x ) L  m + 1 senão R  m fim se fim enquanto j  i enquanto ( j > R ) a[ j ]  a[ j-1] j  j – 1 fim enquanto a [ R ]  x fim para ... x = 19 5.1.2. Inserção Binária 75 Introdução à Computação II – 5954006 1 2 3 4 5 6 7 12 43 43 45 56 95 8 a N = 7 i L R m ... para i  2 até i  N x  a [ i ] L  1 R  i enquanto ( L < R ) m  floor ( ( L + R ) / 2) se (a[m] ≤ x ) L  m + 1 senão R  m fim se fim enquanto j  i enquanto ( j > R ) a[ j ]  a[ j-1] j  j – 1 fim enquanto a [ R ]  x fim para ... x = 19 5.1.2. Inserção Binária 76 Introdução à Computação II – 5954006 1 2 3 4 5 6 7 12 19 43 45 56 95 8 a N = 8 i L R m ... para i  2 até i  N x  a [ i ] L  1 R  i enquanto ( L < R ) m  floor ( ( L + R ) / 2) se (a[m] ≤ x ) L  m + 1 senão R  m fim se fim enquanto j  i enquanto ( j > R ) a[ j ]  a[ j-1] j  j – 1 fim enquanto a [ R ]  x fim para ... x = 19 5.1.2. Inserção Binária 77 Introdução à Computação II – 5954006 1 2 3 4 5 6 7 12 19 43 45 56 95 8 a N = 7 i L R m ... para i  2 até i  N x  a [ i ] L  1 R  i enquanto ( L < R ) m  floor ( ( L + R ) / 2) se (a[m] ≤ x ) L  m + 1 senão R  m fim se fim enquanto j  i enquanto ( j > R ) a[ j ]  a[ j-1] j  j – 1 fim enquanto a [ R ]  x fim para ... x = 8 5.1.2. Inserção Binária 78 Introdução à Computação II – 5954006 1 2 3 4 5 6 7 12 19 43 45 56 95 8 a N = 7 i L R m ... para i  2 até i  N x  a [ i ] L  1 R  i enquanto ( L < R ) m  floor ( ( L + R ) / 2) se (a[m] ≤ x ) L  m + 1 senão R  m fim se fim enquanto j  i enquanto ( j > R ) a[ j ]  a[ j-1] j  j – 1 fim enquanto a [ R ]  x fim para ... x = 8 5.1.2. Inserção Binária 79 Introdução à Computação II – 5954006 1 2 3 4 5 6 7 12 19 43 45 56 95 8 a N = 7 i L R m ... para i  2 até i  N x  a [ i ] L  1 R  i enquanto ( L < R ) m  floor ( ( L + R ) / 2) se (a[m] ≤ x ) L  m + 1 senão R  m fim se fim enquanto j  i enquanto ( j > R ) a[ j ]  a[ j-1] j  j – 1 fim enquanto a [ R ]  x fim para ... x = 8 5.1.2. Inserção Binária 80 Introdução à Computação II – 5954006 1 2 3 4 5 6 7 12 19 43 45 56 95 8 a N = 7 i L R m j ... para i  2 até i  N x  a [ i ] L  1 R  i enquanto ( L < R ) m  floor ( ( L + R ) / 2) se (a[m] ≤ x ) L  m + 1 senão R  m fim se fim enquanto j  i enquanto ( j > R ) a[ j ]  a[ j-1] j  j – 1 fim enquanto a [ R ]  x fim para ... x = 8 5.1.2. Inserção Binária 81 Introdução à Computação II – 5954006 1 2 3 4 5 6 7 12 19 43 45 56 95 95 a N = 7 i L R m j ... para i  2 até i  N x  a [ i ] L  1 R  i enquanto ( L < R ) m  floor ( ( L + R ) / 2) se (a[m] ≤ x ) L  m + 1 senão R  m fim se fim enquanto j  i enquanto ( j > R ) a[ j ]  a[ j-1] j  j – 1 fim enquanto a [ R ]  x fim para ... x = 8 5.1.2. Inserção Binária 82 Introdução à Computação II – 5954006 1 2 3 4 5 6 7 12 19 43 45 56 56 95 a N = 7 i L R m j ... para i  2 até i  N x  a [ i ] L  1 R  i enquanto ( L < R ) m  floor ( ( L + R ) / 2) se (a[m] ≤ x ) L  m + 1 senão R  m fim se fim enquanto j  i enquanto ( j > R ) a[ j ]  a[ j-1] j  j – 1 fim enquanto a [ R ]  x fim para ... x = 8 5.1.2. Inserção Binária 83 Introdução à Computação II – 5954006 1 2 3 4 5 6 7 12 19 43 45 45 56 95 a N = 7 i L R m j ... para i  2 até i  N x  a [ i ] L  1 R  i enquanto ( L < R ) m  floor ( ( L + R ) / 2) se (a[m] ≤ x ) L  m + 1 senão R  m fim se fim enquanto j  i enquanto ( j > R ) a[ j ]  a[ j-1] j  j – 1 fim enquanto a [ R ]  x fim para ... x = 8 5.1.2. Inserção Binária 84 Introdução à Computação II – 5954006 1 2 3 4 5 6 7 12 19 43 43 45 56 95 a N = 7 i L R m j ... para i  2 até i  N x  a [ i ] L  1 R  i enquanto ( L < R ) m  floor ( ( L + R ) / 2) se (a[m] ≤ x ) L  m + 1 senão R  m fim se fim enquanto j  i enquanto ( j > R ) a[ j ]  a[ j-1] j  j – 1 fim enquanto a [ R ]  x fim para ... x = 8 5.1.2. Inserção Binária 85 Introdução à Computação II – 5954006 1 2 3 4 5 6 7 12 19 19 43 45 56 95 a N = 7 i L R m j ... para i  2 até i  N x  a [ i ] L  1 R  i enquanto ( L < R ) m  floor ( ( L + R ) / 2) se (a[m] ≤ x ) L  m + 1 senão R  m fim se fim enquanto j  i enquanto ( j > R ) a[ j ]  a[ j-1] j  j – 1 fim enquanto a [ R ]  x fim para ... x = 8 5.1.2. Inserção Binária 86 Introdução à Computação II – 5954006 1 2 3 4 5 6 7 12 12 19 43 45 56 95 a N = 7 i L R m ... para i  2 até i  N x  a [ i ] L  1 R  i enquanto ( L < R ) m  floor ( ( L + R ) / 2) se (a[m] ≤ x ) L  m + 1 senão R  m fim se fim enquanto j  i enquanto ( j > R ) a[ j ]  a[ j-1] j  j – 1 fim enquanto a [ R ]  x fim para ... x = 8 5.1.2. Inserção Binária 87 Introdução à Computação II – 5954006 1 2 3 4 5 6 7 8 12 19 43 45 56 95 a N = 7 i L R m ... para i  2 até i  N x  a [ i ] L  1 R  i enquanto ( L < R ) m  floor ( ( L + R ) / 2) se (a[m] ≤ x ) L  m + 1 senão R  m fim se fim enquanto j  i enquanto ( j > R ) a[ j ]  a[ j-1] j  j – 1 fim enquanto a [ R ]  x fim para ... x = 8 Vetor ordenado! 5.1.2. Inserção Binária 88 Introdução à Computação II – 5954006 • Análise ▪ A posição correta para a inserção é encontrada quando L = R ▪ Para cada intervalo de comprimento i, a operação de bissecção deverá ser aplicada ceil(log(i)) vezes. Assim: ▪ O número de comparações é independente da ordem inicial dos elementos ▪ Entretanto, devido ao truncamento inerente à operação de divisão envolvida na bissecção do intervalo de busca, o número exato de comparações necessárias para a ordenação de i elementos pode ser até uma unidade maior que o esperado ▪ Essa diferença é tal que as posições de inserção próximas da extremidade superior do vetor são, em média, localizadas um pouco mais rapidamente do que as que estão no outro extremo, favorecendo casos em que os elementos originais estão em ordem   ) log ( log log ( ) 2 2 2 2 N O N N N i C N i   = = 5.1.2. Inserção Binária Ver análise na lousa 89 Introdução à Computação II – 5954006 • Análise ▪ A melhoria obtida é referente apenas ao número de comparações, mas não ao número de movimentações ▪ Como, em geral, mover os elementos consome mais tempo do que comparar duas chaves, a melhoria obtida não é de modo algum drástica (da ordem de N2) ➢Esse método mostra que uma “melhoria óbvia”, em geral, possui conseqüências menos drásticas do que se pode pensar à primeira vista 5.1.2. Inserção Binária 90 Introdução à Computação II – 5954006 Exercício 5.1.2. Utilizando o algoritmo de inserção binária, 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.1.2. Inserção Binária 91 Introdução à Computação II – 5954006 Exercício 5.1.2. Solução i Ci Mi 45 56 12 43 95 19 8 67 2 1 2 45 56 12 43 95 19 8 67 3 2 4 12 45 56 43 95 19 8 67 4 2 4 12 43 45 56 95 19 8 67 5 2 2 12 43 45 56 95 19 8 67 6 3 6 12 19 43 45 56 95 8 67 7 3 8 8 12 19 43 45 56 95 67 8 3 3 8 12 19 43 45 56 67 95 16 29 i Ci Mi 8 12 19 43 45 56 67 95 2 1 2 8 12 19 43 45 56 67 95 3 1 2 8 12 19 43 45 56 67 95 4 2 2 8 12 19 43 45 56 67 95 5 2 2 8 12 19 43 45 56 67 95 6 2 2 8 12 19 43 45 56 67 95 7 2 2 8 12 19 43 45 56 67 95 8 3 2 8 12 19 43 45 56 67 95 13 14 i Ci Mi 95 67 56 45 43 19 12 8 2 1 3 67 95 56 45 43 19 12 8 3 2 4 56 67 95 45 43 19 12 8 4 2 5 45 56 67 95 43 19 12 8 5 3 6 43 45 56 67 95 19 12 8 6 3 7 19 43 45 56 67 95 12 8 7 3 8 12 19 43 45 56 67 95 8 8 3 9 8 12 19 43 45 56 67 95 17 42 i Ci Mi 19 12 8 45 43 56 67 95 2 1 3 12 19 8 45 43 56 67 95 3 2 4 8 12 19 45 43 56 67 95 4 2 2 8 12 19 45 43 56 67 95 5 2 3 8 12 19 43 45 56 67 95 6 2 2 8 12 19 43 45 56 67 95 7 2 2 8 12 19 43 45 56 67 95 8 3 2 8 12 19 43 45 56 67 95 14 18 5.1.2. Inserção Binária 92 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