apostila

10.18) 10 100 10000 100000000
Busca bina´ria (fig. 10.20) 3 5 10 19
Figura 10.19: Tabela resumindo nu´mero de comparac¸o˜es para algoritmos de busca.
10.1. VETORES 143
function busca (x: real ; var v: vetor r ; n: integer) : integer ;
var inicio , fim , meio: integer ;
begin
inicio :=1; (∗ aponta para o inicio do vetor ∗)
fim:= n; (∗ aponta para o fim do vetor ∗)
meio:= ( inicio + fim) div 2; (∗ aponta para o meio do vetor ∗)
while (v[meio] <> x) and (fim >= inicio ) do
begin
if v[meio] > x then (∗ vai jogar uma das duas metades fora ∗)
fim:= meio − 1 (∗ metade superior foi jogada fora ∗)
else
inicio:= meio + 1;(∗ metade inferior foi jogada fora ∗)
meio:= ( inicio + fim) div 2; (∗ recalcula apontador para meio ∗)
end;
(∗ o laco termina quando achou ou quando o fim ficou antes do inicio ∗)
i f v[meio] = x then
busca:= meio
else
busca:= 0;
end;
Figura 10.20: Busca bina´ria.
O importante do me´todo da busca bina´ria e´ que ela apresenta um cara´ter lo-
gar´ıtmico para o pior caso com relac¸a˜o ao tamanho da entrada, o que e´ bastante
significativo. Contudo, e´ absolutamente relevante destacar que este me´todo so´ pode
ser aplicado em vetores ordenados, sena˜o na˜o funciona. A questa˜o e´ saber qual o
custo de se ordenar, ou de se manter ordenado, um vetor. Isto sera´ estudado a` frente.
Manipulando vetores ordenados
Quando operac¸o˜es de inserc¸a˜o e remoc¸a˜o sa˜o feitas em vetores ordenados e´ impor-
tante que estas alterac¸o˜es em seus elementos preservem a propriedade do vetor estar
ordenado, por exemplo, para que se possa usar uma busca bina´ria.
A seguir apresentamos soluc¸o˜es para se remover ou inserir um elemento de um
vetor, iniciando pela remoc¸a˜o. O procedimento da figura 10.21 garante a remoc¸a˜o do
elemento que esta´ na posic¸a˜o pos do vetor v que tem tamanho n.
procedure remove (pos : integer ; var v: vetor r ; var n: integer) ;
var i : integer ;
begin
for i := pos to n−1 do
v[ i ]:= v[ i +1];
n:= n − 1;
end;
Figura 10.21: Removendo de um vetor ordenado.
144 CAPI´TULO 10. ESTRUTURAS DE DADOS
Remover elementos na˜o e´ ta˜o trivial quanto parece, pois na˜o podemos deixar
“buracos” no vetor. Este algoritmo enta˜o copia todos os elementos que esta˜o a` frente
daquele que foi removido uma posic¸a˜o para tra´s. Tomemos como exemplo o seguinte
vetor ordenado:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 . . . 197 198 199 200
0 2 7 12 15 18 19 21 23 27 ? ? ? ? ? . . . ? ? ? ?
Para remover o elemento 12, que esta´ na posic¸a˜o 4, todos os outros sa˜o copiados,
um por um. Para na˜o perdermos elementos, este processo tem que iniciar da posic¸a˜o
onde houve a remoc¸a˜o ate´ a penu´ltima posic¸a˜o. O vetor resultante e´ o seguinte:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 . . . 197 198 199 200
0 2 7 15 18 19 21 23 27 27 ? ? ? ? ? . . . ? ? ? ?
O detalhe e´ que o elemento 27 que estava na posic¸a˜o 10 continua la´, mas, como o
vetor agora tem tamanho 9 (pois um elemento foi removido) este u´ltimo 27 agora e´
lixo de memo´ria.
Com relac¸a˜o ao algoritmo de inserc¸a˜o de um elemento em um vetor ordenado,
deve-se primeiro determinar a posic¸a˜o correta de inserc¸a˜o, logo, um processo de busca
deve ser feito, iniciando do comec¸o do vetor (posic¸a˜o 1) ate´ que seja encontrado um
elemento maior que aquele que esta´ se inserindo. Para facilitar esta busca, usamos
uma sentinela.
Tomemos novamente como exemplo o vetor abaixo e consideremos que vamos
inserir o elemento 17.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 . . . 197 198 199 200
0 2 7 12 15 18 19 21 23 27 ? ? ? ? ? . . . ? ? ? ?
A posic¸a˜o correta do 17 e´ logo apo´s o elemento 15, isto e´, na posic¸a˜o 6. Para
abrirmos espac¸o no vetor e ao mesmo tempo na˜o perdermos o 18 que la´ esta´ devemos
copiar todos os elementos, um por um, uma posic¸a˜o para frente. Isto deve ser feito
de tra´s para frente, isto e´, copia-se o u´ltimo uma posic¸a˜o adiante para abrir espac¸o
para colocar o penu´ltimo, e assim por diante. O resultado seria um vetor assim:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 . . . 197 198 199 200
0 2 7 12 15 18 18 19 21 23 27 ? ? ? ? . . . ? ? ? ?
Observe que agora temos duas vezes o 18 no vetor. O primeiro deles agora pode
ser substitu´ıdo pelo novo elemento, o 17, assim:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 . . . 197 198 199 200
0 2 7 12 15 17 18 19 21 23 27 ? ? ? ? . . . ? ? ? ?
10.1. VETORES 145
procedure insere (x: real ; var v: vetor r ; var n: integer) ;
var i : integer ;
begin
v[0]:= x;
i:= n + 1;
while x < v[ i ] do
begin
v[ i+1]:= v[ i ] ;
i := i − 1;
end;
n:= n + 1;
end;
Figura 10.22: Inserindo em um vetor ordenado.
O procedimento da figura 10.22 insere um elemento x no vetor v que tem tamanho
n de maneira que ele continue ordenado. Apenas uma passagem no vetor e´ feita: ao
mesmo tempo em que ele esta´ procurando a posic¸a˜o correta do elemento ele ja´ vai
abrindo espac¸o no vetor.
No caso de vetores na˜o ordenados, os processo de inserc¸a˜o e remoc¸a˜o sa˜o mais
simples. Pode-se sempre inserir um elemento novo no final do vetor e para remover,
basta copiar o u´ltimo sobre o que foi removido.
Ha´ um u´ltimo algoritmo interessante que trabalha com vetores ordenados: a ideia
e´ fundir3 dois vetores ordenados em um terceiro, obtendo-se um vetor ordenado como
resultado contendo os mesmos elementos dos vetores anteriores.
O princ´ıpio deste algoritmo e´: atribui-se a duas varia´veis i e j o ı´ndice 1. Em
seguida se compara os respectivos elementos das posic¸o˜es i em um vetor e j no outro.
Se o elemento do primeiro vetor e´ menor do que o do segundo, ele e´ copiado no terceiro
vetor e o apontador i e´ incrementado de 1, passando a observar o pro´ximo elemento.
Sena˜o, o elemento do segundo vetor e´ menor e portanto este que e´ copiado para o
terceiro vetor e o apontador j que e´ incrementado. Quando um dos dois vetores
acabar, basta copiar o restante do outro no terceiro vetor. Um apontador k controla
o terceiro vetor. Este e´ sempre incrementado a cada co´pia.
Vejamos isto atrave´s de um exemplo. Consideremos os seguintes dois vetores
ordenados e um terceiro que vai receber a fusa˜o dos dois.
i=1 2 3 4 5
v: 2 4 5 7 9
j=1 2 3
w: 1 3 6
k=1 2 3 4 5 6 7 8
r:
3Em ingleˆs, merge
146 CAPI´TULO 10. ESTRUTURAS DE DADOS
comparam-se o elementos apontados por i e j. Como 1 < 2, copia-se o 1 no vetor r e
incrementa-se o apontador j, assim:
i=1 2 3 4 5
v: 2 4 5 7 9
1 j=2 3
w: 1 3 6
1 k=2 3 4 5 6 7 8
r: 1
Agora comparam-se o elementos apontados por i e j. Como 2 < 3, copia-se o 2 no
vetor r e incrementa-se o apontador i, assim:
1 i=2 3 4 5
v: 2 4 5 7 9
1 j=2 3
w: 1 3 6
1 2 k=3 4 5 6 7 8
r: 1 2
Repetindo-se este processo mais algumas vezes chegaremos no seguinte estado:
1 2 3 i=4 5
v: 2 4 5 7 9
1 2 j=3
w: 1 3 6
1 2 3 4 k=5 6 7 8
r: 1 2 3 4 5
Neste ponto o 6 sera´ copiado em r e o vetor w termina. Basta copiar o que sobrou
de v e terminar o processo, o que resultara´ no seguinte:
1 2 3 4 5 i=6
v: 2 4 5 7 9
1 2 3 j=4
w: 1 3 6
1 2 3 4 5 6 7 8 k=9
r: 1 2 3 4 5 6 7 9
O algoritmo da figura 10.23 implementa o que foi discutido, e´ eficiente e varre os
dois vetores apenas uma vez.
10.1. VETORES 147
procedure merge (var v: vetor r ; n: integer ; var w: vetor r ; m: integer ; r : vetor r) ;
var i , j , k, l : integer ;
begin
i := 1; j:= 1; k:= 1;
(∗ i vai controlar os elementos de v ∗)
(∗ j vai controlar os elementos de w ∗)
(∗ k vai controlar os elementos do vetor resultante da fusao , r ∗)
while ( i <= n) and ( j <= m) do
begin
if v[ i ] <= w[ j ] then (∗ se o elemento de v dh menor que o de w ∗)
begin
r [k]:= v[ i ] ;
i := i + 1;
end
else (∗ o elemento de w eh menor que o de v ∗)
begin
r [k]:= w[ j ] ;
j:= j + 1;
end;
k:= k + 1; (∗ k eh sempre incrementado ∗)
end;
(∗ quando sai do laco , um dos dois vetores acabou ∗)
i f i <= n