apostila

then (\u2217 w acabou, copiar o restante de v em r \u2217)
for l := i to n do
begin
r [k]:= v[ l ] ;
k:= k + 1;
end;
else (\u2217 v acabou, copiar o restante de w em r \u2217)
for l := i to m do
begin
r [k]:= w[ l ] ;
k:= k + 1;
end;
end;
Figura 10.23: Fundindo dois vetores ordenados.
148 CAPI´TULO 10. ESTRUTURAS DE DADOS
10.1.4 Ordenac¸a\u2dco em vetores
Ordenar vetores e´ extremamente importante em computac¸a\u2dco, pois e´ muito comum
que uma sa´\u131da de um programa seja dado com algum tipo de ordem sobre os dados.
Nesta sec¸a\u2dco vamos apresentar dois algoritmos para este problema: os me´todos da
ordenac¸a\u2dco por selec¸a\u2dco e por inserc¸a\u2dco.
Ordenac¸a\u2dco por selec¸a\u2dco
A ordenac¸a\u2dco por selec¸a\u2dco e´ um me´todo bastante simples de se compreender e tambe´m
de se implementar.
O princ´\u131pio e´ selecionar os elementos corretos para cada posic¸a\u2dco do vetor, da´\u131 o
nome do me´todo. Para um vetor de N elementos, existem N \u2212 1 etapas. Em cada
etapa i o i-e´simo menor elemento e´ selecionado e colocado na posic¸a\u2dco i.
Assim, na primeira etapa, o menor elemento de todos e´ localizado (selecionado) e
colocado na primeira posic¸a\u2dco do vetor. Na segunda etapa localiza-se o segundo menor
e coloca-se na segunda posic¸a\u2dco, e assim por diante, ate´ que, por fim, o penu´ltimo
menor elemento (isto e´, o segundo maior) e´ colocado na penu´ltima posic¸a\u2dco. Con-
sequentemente, como ja´ temos N \u2212 1 elementos em seus devidos lugares, o u´ltimo
tambe´m esta´. Vejamos um exemplo de um vetor com 10 elementos.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 . . . 197 198 199 200
15 12 27 23 7 2 0 18 19 21 ? ? ? ? ? . . . ? ? ? ?
Para localizarmos o menor elemento, que e´ o zero que esta´ na posic¸a\u2dco 7 do vetor,
so´ ha´ uma maneira, que e´ percorrer todo o vetor e localizar o menor. Este deve ser
colocado na primeira posic¸a\u2dco. Este u´ltimo (o 15), por sua vez, deve ser trocado de
posic¸a\u2dco com o da posic¸a\u2dco 7. Por isto a busca pelo menor deve nos retornar o \u131´ndice do
menor elemento e na\u2dco o elemento em s´\u131. O resultado da primeira etapa deste processo
esta´ mostrado na figura abaixo, com destaque para os elementos trocados.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 . . . 197 198 199 200
0 12 27 23 7 2 15 18 19 21 ? ? ? ? ? . . . ? ? ? ?
Neste ponto precisamos do segundo menor. Por construc¸a\u2dco lo´gica do algoritmo,
basta percorrer o vetor a partir da segunda posic¸a\u2dco, pois o primeiro ja´ esta´ em seu
lugar. O menor de todos agora e´ o 2, que esta´ na posic¸a\u2dco 6. Basta troca´-lo pelo
segundo elemento, que e´ o 12. E o processo se repete:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 . . . 197 198 199 200
0 2 27 23 7 12 15 18 19 21 ? ? ? ? ? . . . ? ? ? ?
0 2 7 23 27 12 15 18 19 21 ? ? ? ? ? . . . ? ? ? ?
0 2 7 12 27 23 15 18 19 21 ? ? ? ? ? . . . ? ? ? ?
0 2 7 12 15 23 27 18 19 21 ? ? ? ? ? . . . ? ? ? ?
0 2 7 12 15 18 27 23 19 21 ? ? ? ? ? . . . ? ? ? ?
0 2 7 12 15 18 19 23 27 21 ? ? ? ? ? . . . ? ? ? ?
0 2 7 12 15 18 19 21 27 23 ? ? ? ? ? . . . ? ? ? ?
0 2 7 12 15 18 19 21 23 27 ? ? ? ? ? . . . ? ? ? ?
10.1. VETORES 149
procedure selecao (var v: vetor r ; n: integer) ;
var i , j : integer ; aux: real ;
begin
for i := 1 to n\u22121 do
begin
(\u2217 acha a posicao do menor a partir de i \u2217)
pos menor:= i ;
for j:= i+1 to n do (\u2217 inicia a partir de i+1 \u2217)
i f v[ j ] < v[pos menor] then
pos menor:= j ;
aux:= v[pos menor ] ; (\u2217 troca os elementos \u2217)
v[pos menor]:= v[ i ] ;
v[ i ]:= aux;
end;
end;
Figura 10.24: Me´todo de ordenac¸a\u2dco por selec¸a\u2dco.
A figura 10.24 mostra a versa\u2dco em Pascal deste algoritmo.
Este algoritmo tem algumas particularidades dignas de nota. A primeira e´ que, em
cada etapa i, a ordenac¸a\u2dco dos primeiros i\u2212 1 elementos e´ definitiva, isto e´, constitui
a ordenac¸a\u2dco final destes primeiros i elementos do vetor.
A segunda e´ que a busca pelo menor elemento em cada etapa i exige percorrer
um vetor de N \u2212 i elementos. Como isto e´ feito N vezes, enta\u2dco o nu´mero de com-
parac¸o\u2dces feitas na parte mais interna do algoritmo e´ sempre N(N\u22121)
2
, o que define um
comportamento quadra´tico para as comparac¸o\u2dces.
A terceira e´ que trocas de posic¸o\u2dces no vetor ocorrem no lac¸o mais externo, por
isto o nu´mero total de trocas feitas pelo algoritmo e´ sempre N \u2212 1.
Ordenac¸a\u2dco por inserc¸a\u2dco
A ordenac¸a\u2dco por inserc¸a\u2dco e´ provavelmente a mais eficiente, na pra´tica, que a ordenac¸a\u2dco
por selec¸a\u2dco. Pore´m, embora o algoritmo em s´\u131 seja simples, sua implementac¸a\u2dco e´
repleta de detalhes. Vamos inicialmente entender o processo.
O princ´\u131pio do algoritmo e´ percorrer o vetor e a cada etapa i, o elemento da
posic¸a\u2dco i e´ inserido (da´\u131 o nome do me´todo) na sua posic¸a\u2dco correta relativamente
quando comparado aos primeiros i\u2212 1 elementos.
Para melhor compreensa\u2dco, faremos a apresentac¸a\u2dco de um exemplo sem mostrarmos
o vetor, usaremos seque\u2c6ncias de nu´meros. Consideremos que a entrada e´ a mesma do
exemplo anterior, isto e´:
15, 12, 27, 23, 7, 2, 0, 18, 19, 21.
Na primeira etapa o algoritmo considera que o primeiro elemento, o 15, esta´ na
sua posic¸a\u2dco relativa correta, pois se considera apenas a primeira posic¸a\u2dco do vetor.
Usaremos os negritos para mostrar quais as etapas ja´ foram feitas pelo algoritmo.
150 CAPI´TULO 10. ESTRUTURAS DE DADOS
Na segunda etapa deve-se inserir o segundo elemento em sua posic¸a\u2dco relativa cor-
reta considerando-se apenas o vetor de tamanho 2. Como o 12 e´ menor que que o 15,
deve-se trocar estes elementos de posic¸a\u2dco, nos resultando na seque\u2c6ncia:
12, 15, 27, 23, 7, 2, 0, 18, 19, 21.
Neste ponto, os elementos 12 e 15 esta\u2dco em suas posic¸o\u2dces relativas corretas considerando-
se um vetor de 2 posic¸o\u2dces. Agora, deve-se colocar o 27 no vetor de 3 elementos. Mas
o 27 ja´ esta´ em seu lugar relativo, enta\u2dco o algoritmo na\u2dco faz nada:
12, 15, 27, 23, 7, 2, 0, 18, 19, 21.
Na quarta etapa deve-se inserir o 23 na sua posic¸a\u2dco relativa correta considerando-se
um vetor de 4 elementos. O 23 tem que estar entre o 15 e o 27:
12, 15, 23, 27, 7, 2, 0, 18, 19, 21.
Na quinta etapa deve-se inserir o 7 na sua posic¸a\u2dco relativa a um vetor de 5 ele-
mentos. Ele deve ser inserido antes do 12, isto e´, na primeira posic¸a\u2dco:
7, 12, 15, 23, 27, 2, 0, 18, 19, 21.
A situac¸a\u2dco para o 2 e´ similar, deve ser inserido antes do 7, isto e´, no in´\u131cio:
2, 7, 12, 15, 23, 27, 0, 18, 19, 21.
Idem para o zero:
0, 2, 7, 12, 15, 23, 27, 18, 19, 21.
Agora e´ a vez de inserirmos o 18, entre o 15 e o 27:
0, 2, 7, 12, 15, 18, 23, 27, 19, 21.
Na penu´ltima etapa inserimos o 19 entre o 18 e o 23:
0, 2, 7, 12, 15, 18, 19, 23, 27, 21.
E por u´ltimo o 21 entre o 19 e o 23:
0, 2, 7, 12, 15, 18, 19, 21, 23, 27.
Esta seque\u2c6ncia de N passos e´ de fa´cil compreensa\u2dco. Se fo\u2c6ssemos executar com
um conjunto de cartas na ma\u2dco, por exemplo, com cartas de baralho, imaginando um
mac¸o de cartas virado na mesa, basta pegar as cartas uma a uma e encaixar no lugar
certo. As cartas de baralho sa\u2dco facilmente manipuladas para permitir uma inserc¸a\u2dco
em qualquer posic¸a\u2dco.
Infelizmente esta operac¸a\u2dco executada em um vetor na\u2dco e´ ta\u2dco simples. Vamos consi-
derar como exemplo a etapa 8 acima, isto e´, inserc¸a\u2dco do 18 no lugar certo. Retomemos
este caso agora considerando um vetor para melhor ilustrac¸a\u2dco, com destaque para o
elemento 18 que deve nesta etapa ser inserido no lugar certo:
10.1. VETORES 151
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 . . . 197 198 199 200
0 2 7 12 15 23 27 18 19 21 ? ? ? ? ? . . . ? ? ? ?
A posic¸a\u2dco correta do 18, como vimos, e´ entre o 15 e o 23, isto e´, na sexta posic¸a\u2dco
do vetor. Significa que os elementos das posic¸o\u2dces 6 e 7 devem ser movidos um para
frente para abrir espac¸o no vetor para inserc¸a\u2dco do 18. Os elementos das posic¸o\u2dces 9
em diante na\u2dco va\u2dco mudar de lugar. Executando esta operac¸a\u2dco, e salvando o 18 em
alguma varia´vel tempora´ria, obteremos o seguinte vetor:
1 2 3 4 5