APROG Algoritmia e Programação Civilasilva/page14/page16/assets/Teoricas APROG... · comparação em relação ao conteúdo do elemento seguinte e assim sucessivamente até que

Pesquisa e Ordenação de Vectores

APROGCivil

ISEP-DEI, António Silva, © 2007ISEP-DEI, Nelson Freire © 2002

Algoritmia e Programação



APROGCivil


Conteúdo

● Pesquisa em VectoresApresentação e discussão de vários algoritmos de pesquisa.

● Pesquisa linear ou sequencial● Pesquisa binária

● Ordenação de Vectores● Exemplos de aplicação


APROGCivil


Pesquisa

● Existem diversos métodos para pesquisar informação contida em vectores, entre os quais:

– Pesquisa Linear (ou sequencial)● Simples

● Em média, bastante lenta e ineficiente

– Pesquisa Binária● Mais rápida e eficiente

● Exige que os elementos do vector estejam ordenados

O método consiste em colocarmo-nos no 1º elemento do vector e comparar o conteúdo desse elemento com o valor a procurar. Caso sejam iguais a busca terminou; em caso contrário, far-se-á a mesma comparação em relação ao conteúdo do elemento seguinte e assim sucessivamente até que a busca obtenha sucesso, ou até que o último elemento do vector tenha sido alcançado.


APROGCivil


Pesquisa Linear

Parte-se do princípio que não há valores repetidos ou apenas nos i n te ressa encontrar a 1ª ocorrência.

35

12 5 35 92 102 57 23 48

0 1 2 3 4 5 6 7

v

i

p

v(0) = p?

v(1) = p?

v(2) = p?Sim

Não

Não


APROGCivil


Pesquisa Linear - Mecanismo

Encontrado!(na 3ª posição)


APROGCivil


Exemplo - Interface

lstVector

lblBusca

cmdGo

cmdPesquisa

InputBox para preenchimento do vector InputBox para introdução do valor a pesquisar

Private Sub cmdGo_Click() Dim i As Integer, texto As String lstVector.Clear For i = 0 To N - 1 texto = "Vec(" + str(i) + "):" vec(i) = Val(InputBox(texto, "Entrada de Dados")) lstVector.AddItem vec(i) Next i End Sub


APROGCivil


Exemplo - Código

Private Sub cmdPesquisa_Click() Dim i As Integer, num As Integer num = Val(InputBox("Valor a pesquisar:", "Pesquisa")) i = 0 Do Until (num = vec(i)) Or (i > N - 1) i = i + 1 Loop If i < N Then lblBusca.Caption = "Encontrado na posição" + str(i + 1) Else lblBusca.Caption = "Não encontrado" End If End Sub

Ciclo de Pesquisa

Determinação da razão para o fim do ciclo

Procura até encontrar ou até chegar ao fim do vector!

Const N = 10 As IntegerDim vec(N) as Integer

• A pesquisa binária é mais rápida que pesquisa sequencial.• Exige, porém, que os elementos do vector estejam

ordenados (por ordem ascendente ou descendente).• O método consiste em pesquisar sucessivamente os

elementos situados a meio de subintervalos do vector, que irão sendo reduzidos a metade:‣ Começa-se por verificar o elemento a meio do vector. ‣ Se não for o valor procurado, então este só pode estar na

metade inferior ou superior do vector, já que o vector está ordenado.

‣ A segunda pesquisa incidirá apenas sobre metade do vector.

‣ Este processo repete-se até se encontrar o elemento desejado (sucesso) ou determinar que não se encontra no vector (insucesso).


APROGCivil


Pesquisa Binária


APROGCivil


Pesquisa Binária


APROGCivil


Pesquisa Binária

Private Sub cmdPesquisa_Click() Dim num As Integer, inf As Integer, sup As Integer, med As Integer Dim encontrado As Boolean num = Val(InputBox("Valor a pesquisar:", "Pesquisa em Vector")) encontrado = False inf = 0 sup = N - 1 Do While inf <= sup And Not encontrado

med = (inf + sup) \ 2 If num > vec(med) Then

inf = med + 1 ElseIf num < vec(med) Then

sup = med – 1 Else

encontrado = True End If

Loop If encontrado = True Then

lblBusca.Caption = "Encontrado na posição" + str(med + 1) Else

lblBusca.Caption = "Não encontrado" End If End Sub


APROGCivil


Pesquisa Binária - Código

Cálculo da posição médiaSe num é maior que o valor do meio do vectorEntão passamos a procurar na metade superiorSenão, se num é menor que o valor do meioEntão passamos a procurar na metade inferior

Senão, é porque encontramos o valor no vector!

Inicialização dos limites inferior e superior

Procura-se até encontrar ou até chegar ao fim

Pretende-se saber se o valor contido em num se encontra no vector vec.

• Um dos métodos mais simples para ordenar vectores é o da ordenação por selecção.

• Consiste em posicionarmo-nos no 1º elemento do vector e comparar o seu conteúdo com todos os outros.

• Sempre que se encontrar um elemento cujo valor seja menor que o da 1ª posição então os valores serão trocados entre si.

• Quando a comparação do 1º elemento do vector com todos os outros terminar temos a garantia de que o valor desse elemento é já o menor de todos.

• Nesta altura avança-se para o 2º elemento e compara-se o seu conteúdo com todos os elementos que se lhe seguem (3º, 4º, ...) trocando os valores sempre que se encontre um que seja menor.

• Este processo repete-se até se chegar ao fim do vector, altura em que a ordenação do vector estará concluída.


APROGCivil


Ordenação de vectores


APROGCivil


Ordenação por Selecção - I

[ Continua...]


APROGCivil


Ordenação por Selecção - II

Private Sub cmdOrdenar_Click() Dim i As Integer Dim j As Integer Dim temp As Integer For i = 0 To N - 2

For j = i + 1 To N - 1 If vec(j) < vec(i) Then

temp = vec(i) vec(i) = vec(j) vec(j) = temp

End If Next j

Next i For i = 0 To N - 1

lstVectorOrdenado.AddItem vec(i) Next End Sub


APROGCivil


Ordenação por Selecção - Código

Pretende-se obter isto:

a partir disto:

Const N As Integer = 9 Dim vec(N) As Integer

cmdGo

cmdOrdenar

Declarações Globais

Troca de conteúdo entre vec(i) e vec(j)

Documents

APROG Algoritmia e Programação Civilasilva/page14/page16/assets/Teoricas APROG... · comparação em relação ao conteúdo do elemento seguinte e assim sucessivamente até que