Projeto e Análise de Algoritmos Lista 2

1  |PROCEDIMENTO BuscaLinear(A[], X : Inteiro):
2  |VAR
3  |  |i : Inteiro
4  |INICIO
5  |  |PARA i <- 1 ATÉ Comprimento(A) - 1, FAÇA:
6  |  |  |SE X = A[i], ENTÃO:
7  |  |  |  |Retorne i
8  |  |  |FIM-SE
9  |  |FIM-PARA
10 |FIM

• Propriedade invariante) Se X está contido em A, então X está em um sub-vetor A[i..n-1]

• Inicialização) Antes da primeira iteração, temos que i = 1, logo A[1..n-1], portanto o invariante é triivialmente verdadeiro.

• Manutenção) Supondo que o invariante é verdadeiro antes da i-ésima iteração, temos que na i-ésima iteração o laço para (linhas 5 até 9) faz a variável i assumir os valores de 1 até n-1. As linhas 6 a 8 realizam a comparação se A[i] = X | X é a chave. Caso verdadeiro, o procedimento será encerrado com o valor retornado. Caso contrário, o laço continuará até i = n-1. Desta forma, dada uma posição i até n-1 no vetor A[i..n-1] pela propriedade invariante é verdadeiro.

• Finalização) Após a i-ésima iteração do laço inariante no intervalo [i..n-1], pela propriedade inariante, X está contido em A[i..n-1], então X será retornado.

• a) O laço com i = 1 até o comprimento de A - 1.
• b) Pela propriedade invariante, o subvetor dos elementos de A[1..i-1] contém os menores elementos ordenados. Assim, é necessário ser executado apenas para os n-1 primeiros elementos, pois, o n-ésimo elemento é um espaço em branco (NULO).
• c) Melhor caso: \(\Omega(n)\), Pior caso: \(O(n^{2})\). Para um conjunto de dados de array não ordenado tanto inversamente quanto crescente em ordem, o array realizará \(n^{2}\) comparações dos elementos se A[j] < A[min]. Logo, o caso médio é \(\Theta(n^{2})\)

É necessário provar a manutenção a fim de verificar se a propriedade invariante é verdadeira durante a execução do laço.

• Propriedade invariante) Na j-ésima iteração, temos que A[j..n] contém os n-i-maiores elementos ordenados.

• Inicialização) A variável j é inicializada para n, logo o subvetor de [j..n], ou seja, [n..n], compreende apenas um elemento, deste modo é trivialmente ordenado e a propriedade invariante é trivialmente verdadeira.

• Manutenção) Supondo que a propriedade invariante é verdadeira antes da j-ésima iteração, temos que: durante o laço, é comparado se A[j] é menor do que A[j-1], caso verdadeiro, A[j] e A[j-1] trocam de posição, logo, A[j-1] < A[j] < A[j+1] < … < A[n]. Desta forma, o subvetor [j..n] está ordenado com os maiores elementos.

• Finalização) Após a n-ésima iteração, j = i + 1, segundo a propriedade invariante o subvetor [j..n] estará ordenado. [i+1..n] compreende todo o vetor.

1  |PROCEDIMENTO BubbleSort(A[] : Inteiro):
2  |VAR
3  |  |i, j, t : Inteiro
4  |INICIO
5  |  |PARA i <- Comprimento(A) ATÉ 1, FAÇA:
6  |  |  |PARA j <- 2, ATÉ i, FAÇA:
7  |  |  |  |SE A[j - 1] > A[j], ENTÃO:
8  |  |  |  |  |t <- A[j - 1]
9  |  |  |  |  |A[j - 1] <- A[j]
10 |  |  |  |  |A[j] <- t
11 |  |  |  |FIM-SE
12 |  |  |FIM-PARA
13 |  |FIM-PARA
14 |FIM

A i-ésima iteração do laço para das linhas 5 até 13 resultará em n-i iterações no laço das linhas 6 até 12, onde a troca será feita em tempo constante de execução. Assim, o pior caso do bubble sort é \(\Theta(n^{2})\) que é o mesmo que o pior caso de execução do insertion sort.