apostila
259 pág.

apostila

Disciplina:Algoritmos e Estrutura de Dados I542 materiais7.968 seguidores
Pré-visualização50 páginas
6 7 8 9 10 11 12 13 14 15 . . . 197 198 199 200
0 2 7 12 15 23 23 27 19 21 ? ? ? ? ? . . . ? ? ? ?

Isto e´, o 27 foi copiado da posic¸a˜o 7 para a posic¸a˜o 8 e o 23 foi copiado da posic¸a˜o
6 para a posic¸a˜o 7. Na figura acima destacamos os elementos que foram movidos de
lugar. Observando que o 23 ficou repetido na posic¸a˜o 6, o que na pra´tica resultou na
posic¸a˜o 6 livre. Agora basta inserir o 18 a´ı:

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 23 27 19 21 ? ? ? ? ? . . . ? ? ? ?

Esta etapa constitui o nu´cleo do algoritmo mostrado na figura 10.25. O lac¸o
externo apenas garante que esta operac¸a˜o sera´ executada para todos os elementos das
posic¸o˜es de 1 ate´ N .

O lac¸o interno foi implementado de tal forma que, ao mesmo tempo em que se
localiza o lugar certo do elemento da vez, ja´ se abre espac¸o no vetor. O lac¸o e´
controlado por dois testes, um deles para garantir que o algoritmo na˜o extrapole o
in´ıcio do vetor, o outro que compara dois elementos e troca de posic¸a˜o sempre que for
detectado que o elemento esta´ na posic¸a˜o incorreta.

procedure insercao (var v: vetor ; n: integer) ;
var i , j : integer ;

aux: real ;

begin
for i := 1 to n do
begin

aux = v[ i ] ;

(∗ abre espaco no vetor enquanto localiza a posicao certa ∗)
j:= i − 1;
while ( j >= 1) and (v[ j ] > aux) do
begin

v[ j+1] = v[ j ] ;
j:= j − 1;

end;
v[ j+1] = aux;

end;
end;

Figura 10.25: Me´todo de ordenac¸a˜o por inserc¸a˜o.

152 CAPI´TULO 10. ESTRUTURAS DE DADOS

Analisar quantas comparac¸o˜es sa˜o feitas e´ bem mais complicado neste algoritmo,
pois isto depende da configurac¸a˜o do vetor de entrada. Neste nosso exemplo, vimos
que cada etapa teve um comportamento diferente das outras. Em uma vez o elemento
ja´ estava em seu lugar. Em duas outras vezes tivemos que percorrer todo o subvetor
inicial, pois os elementos deveriam ser o primeiro, em cada etapa.

Aparentemente, no pior caso poss´ıvel, que e´ quando o vetor esta´ na ordem inversa
da ordenac¸a˜o, havera´ o maior nu´mero de comparac¸o˜es, que e´ quadra´tico. Mas, na
pra´tica, este algoritmo aparenta ser mais ra´pido que o me´todo da selec¸a˜o na maior
parte dos casos, pois algumas vezes o elemento muda pouco de posic¸a˜o.4

10.1.5 Outros algoritmos com vetores

Nesta sec¸a˜o vamos apresentar alguns problemas interessantes que podem ser resolvidos
usando-se a estrutura de vetores.

Permutac¸o˜es

Vamos apresentar um problema matema´tico conhecido como permutac¸a˜o, propor uma
representac¸a˜o computacional em termos de vetores, e, em seguida, estudar alguns
problemas interessantes do ponto de vista de computac¸a˜o.5

Os matema´ticos definem uma permutac¸a˜o de algum conjunto como uma func¸a˜o
bijetora de um conjunto nele mesmo. Em outras palavras, e´ uma maneira de reor-
denar os elementos do conjunto. Por exemplo, podemos definir uma permutac¸a˜o do
conjunto {1, 2, 3, 4, 5 } assim: P (1) = 4, P (2) = 1, P (3) = 5, P (4) = 2, P (5) = 3.
Esquematicamente temos: (

1 2 3 4 5
4 1 5 2 3

)
Outra maneira seria: P (1) = 2, P (2) = 5, P (3) = 1, P (4) = 3, P (5) = 2. Esque-

maticamente: (
1 2 3 4 5
2 5 1 3 2

)
De fato, existem n! maneiras de se reordenar os elementos e obter uma permutac¸a˜o

va´lida. Se n = 5 enta˜o existem 120 permutac¸o˜es.

Modelando permutac¸o˜es

O primeiro problema interessante do ponto de vista algoritmico e´ como representar

4O site http://cg.scs.carleton.ca/~morin/misc/sortalg permite visualizar o comporta-
mento dos principais algoritmos de ordenac¸a˜o atrave´s de animac¸o˜es. Os dois algoritmos aqui ex-
plicados esta˜o la´, entre outros.

5Esta sec¸a˜o foi inspirada em uma preparato´ria para a maratona de programac¸a˜o da ACM da
Ural State Universisy (Internal Contest October’2000 Junior Session) encontrada na seguinte URL:
http://acm.timus.ru/problem.aspx?space=1&num=1024.

10.1. VETORES 153

uma permutac¸a˜o. Para isto pode-se usar um vetor de n posic¸o˜es inteiras, onde cada
posic¸a˜o e´ um valor (sem repetic¸a˜o) entre 1 e n. Em todos os algoritmos desta sec¸a˜o
consideraremos que:

const min i = 1; max i = 5;

Assim os dois vetores que representam as permutac¸o˜es acima sa˜o, respectivamente:

1 2 3 4 5
4 1 5 2 3

1 2 3 4 5
2 5 1 3 2

Testando permutac¸o˜es va´lidas

Uma vez resolvido o problema da representac¸a˜o, podemos estudar o pro´ximo de-
safio, que e´ como testar se um dado vetor (lido do teclado) e´ uma permutac¸a˜o va´lida?

O algoritmo tem que testar se, para os ı´ndices de 1 a n, seus elementos sa˜o cons-
titu´ıdos por todos, e apenas, os elementos entre 1 e n, em qualquer ordem. A func¸a˜o
da figura 10.26 apresenta uma poss´ıvel soluc¸a˜o.

function testa permutacao (var v: vetor i ; n: integer) : boolean;
var i , j : integer ;

eh permutacao: boolean;

begin
eh permutacao:= true ;
i := 1;
while eh permutacao and ( i <= n) do
begin

j:= 1; (∗ procura se i esta no vetor ∗)
while (v[ j ] <> i ) and ( j <= n) do

j:= j + 1;
i f v[ j ] <> i then (∗ se nao achou nao eh permutacao ∗)

eh permutacao:= false ;
i := i +1;

end;
testa permutacao:= eh permutacao;

end; (∗ testa permutacao ∗)

Figura 10.26: Verifica se um vetor define uma permutac¸a˜o.

Este algoritmo testa para saber se cada ı´ndice entre i e n esta´ presente no vetor.
Para isto executa no pior caso algo da ordem do quadrado do tamanho do vetor.

No primeiro semestre de 2011 um estudante6 sugeriu que basta usar um vetor

6Cre´ditos para o DESCOBRIR O NOME DO ALUNO

154 CAPI´TULO 10. ESTRUTURAS DE DADOS

auxiliar, inicialmente zerado, e percorrer o vetor candidato a permutac¸a˜o apenas uma
vez. Para cada ı´ndice, tentar inserir seu respectivo conteu´do no vetor auxiliar: se esti-
ver com um zero, inserir, sena˜o, na˜o e´ permutac¸a˜o. Se o vetor auxiliar for totalmente
preenchido enta˜o temos um vetor que representa uma permutac¸a˜o. Este processo e´
linear e esta´ ilustrado na figura 10.27.

function testa permutacao (var v: vetor i ; n: integer) : boolean;
var i , j : integer ;

aux: vetor ;
eh permutacao: boolean;

begin
zera vetor (aux,n) ;
eh permutacao:= true ;
i := 1;
while eh permutacao and ( i <= n) do
begin

if aux[v[ i ] ] = 0 then
aux[v[ i ]]:= v[ i ]

else
eh permutacao:= false

i := i + 1;
end;
testa permutacao:= eh permutacao;

end; (∗ testa permutacao ∗)

Figura 10.27: Verifica linearmente se um vetor define uma permutac¸a˜o.

Outros estudantes sugeriram uma conjectura, na˜o provada em sala, de que, se
todos os elementos pertencem ao intervalo 1 ≤ v[i] ≤ n e ∑ni=1 v[i] = n(n+1)2 e ao
mesmo tempo

∏n
i=1 v[i] = n!, enta˜o o vetor representa uma permutac¸a˜o. Tambe´m

na˜o encontramos contra-exemplo e o problema ficou em aberto.

Gerando permutac¸o˜es va´lidas

O pro´ximo problema e´ gerar aleatoriamente uma permutac¸a˜o. Para isto faremos
uso da func¸a˜o random da linguagem Pascal.

O primeiro algoritmo gera um vetor de maneira aleato´ria e depois testa se o vetor
produzido pode ser uma permutac¸a˜o usando o co´digo da func¸a˜o testa permutacao ja´
implementado. A tentativa e´ reaproveitar co´digo a qualquer custo. Este racioc´ınio
esta´ implementado no co´digo da figura 10.28.

Este algoritmo e´ absurdamente lento quando n cresce. Isto ocorre pois os vetores
sa˜o gerados e depois testados para ver se sa˜o va´lidos, mas, conforme esperado, e´
muito prova´vel que nu´meros repetidos sejam gerados em um vetor com grande nu´mero
de elementos. Um dos autores deste material teve pacieˆncia de esperar o co´digo
terminar apenas ate´ valores de n pro´ximos de 14. Para valores maiores o co´digo ficou
infernalmente demorado, levando va´rias horas de processamento.

Numa tentativa de melhorar o desempenho, o que implica em abrir ma˜o da como-

10.1. VETORES 155

procedure gerar permutacao1 (var v: vetor i ; var n: integer) ;
var i : integer ;

begin
read (n) ;
randomize