apostila

then (∗ w acabou, copiar o restante de v em r ∗)
for l := i to n do
begin
r [k]:= v[ l ] ;
k:= k + 1;
end;
else (∗ v acabou, copiar o restante de w em r ∗)
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˜o em vetores
Ordenar vetores e´ extremamente importante em computac¸a˜o, pois e´ muito comum
que uma sa´ıda de um programa seja dado com algum tipo de ordem sobre os dados.
Nesta sec¸a˜o vamos apresentar dois algoritmos para este problema: os me´todos da
ordenac¸a˜o por selec¸a˜o e por inserc¸a˜o.
Ordenac¸a˜o por selec¸a˜o
A ordenac¸a˜o por selec¸a˜o e´ um me´todo bastante simples de se compreender e tambe´m
de se implementar.
O princ´ıpio e´ selecionar os elementos corretos para cada posic¸a˜o do vetor, da´ı o
nome do me´todo. Para um vetor de N elementos, existem N − 1 etapas. Em cada
etapa i o i-e´simo menor elemento e´ selecionado e colocado na posic¸a˜o i.
Assim, na primeira etapa, o menor elemento de todos e´ localizado (selecionado) e
colocado na primeira posic¸a˜o do vetor. Na segunda etapa localiza-se o segundo menor
e coloca-se na segunda posic¸a˜o, 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˜o. Con-
sequentemente, como ja´ temos N − 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˜o 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˜o. Este u´ltimo (o 15), por sua vez, deve ser trocado de
posic¸a˜o com o da posic¸a˜o 7. Por isto a busca pelo menor deve nos retornar o ı´ndice do
menor elemento e na˜o o elemento em s´ı. 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˜o lo´gica do algoritmo,
basta percorrer o vetor a partir da segunda posic¸a˜o, pois o primeiro ja´ esta´ em seu
lugar. O menor de todos agora e´ o 2, que esta´ na posic¸a˜o 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−1 do
begin
(∗ acha a posicao do menor a partir de i ∗)
pos menor:= i ;
for j:= i+1 to n do (∗ inicia a partir de i+1 ∗)
i f v[ j ] < v[pos menor] then
pos menor:= j ;
aux:= v[pos menor ] ; (∗ troca os elementos ∗)
v[pos menor]:= v[ i ] ;
v[ i ]:= aux;
end;
end;
Figura 10.24: Me´todo de ordenac¸a˜o por selec¸a˜o.
A figura 10.24 mostra a versa˜o em Pascal deste algoritmo.
Este algoritmo tem algumas particularidades dignas de nota. A primeira e´ que, em
cada etapa i, a ordenac¸a˜o dos primeiros i− 1 elementos e´ definitiva, isto e´, constitui
a ordenac¸a˜o 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 − i elementos. Como isto e´ feito N vezes, enta˜o o nu´mero de com-
parac¸o˜es feitas na parte mais interna do algoritmo e´ sempre N(N−1)
2
, o que define um
comportamento quadra´tico para as comparac¸o˜es.
A terceira e´ que trocas de posic¸o˜es no vetor ocorrem no lac¸o mais externo, por
isto o nu´mero total de trocas feitas pelo algoritmo e´ sempre N − 1.
Ordenac¸a˜o por inserc¸a˜o
A ordenac¸a˜o por inserc¸a˜o e´ provavelmente a mais eficiente, na pra´tica, que a ordenac¸a˜o
por selec¸a˜o. Pore´m, embora o algoritmo em s´ı seja simples, sua implementac¸a˜o e´
repleta de detalhes. Vamos inicialmente entender o processo.
O princ´ıpio do algoritmo e´ percorrer o vetor e a cada etapa i, o elemento da
posic¸a˜o i e´ inserido (da´ı o nome do me´todo) na sua posic¸a˜o correta relativamente
quando comparado aos primeiros i− 1 elementos.
Para melhor compreensa˜o, faremos a apresentac¸a˜o de um exemplo sem mostrarmos
o vetor, usaremos sequeˆncias 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˜o relativa correta, pois se considera apenas a primeira posic¸a˜o 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˜o 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˜o, nos resultando na sequeˆncia:
12, 15, 27, 23, 7, 2, 0, 18, 19, 21.
Neste ponto, os elementos 12 e 15 esta˜o em suas posic¸o˜es relativas corretas considerando-
se um vetor de 2 posic¸o˜es. Agora, deve-se colocar o 27 no vetor de 3 elementos. Mas
o 27 ja´ esta´ em seu lugar relativo, enta˜o o algoritmo na˜o faz nada:
12, 15, 27, 23, 7, 2, 0, 18, 19, 21.
Na quarta etapa deve-se inserir o 23 na sua posic¸a˜o 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˜o relativa a um vetor de 5 ele-
mentos. Ele deve ser inserido antes do 12, isto e´, na primeira posic¸a˜o:
7, 12, 15, 23, 27, 2, 0, 18, 19, 21.
A situac¸a˜o para o 2 e´ similar, deve ser inserido antes do 7, isto e´, no in´ıcio:
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ˆncia de N passos e´ de fa´cil compreensa˜o. Se foˆssemos executar com
um conjunto de cartas na ma˜o, 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˜o facilmente manipuladas para permitir uma inserc¸a˜o
em qualquer posic¸a˜o.
Infelizmente esta operac¸a˜o executada em um vetor na˜o e´ ta˜o simples. Vamos consi-
derar como exemplo a etapa 8 acima, isto e´, inserc¸a˜o do 18 no lugar certo. Retomemos
este caso agora considerando um vetor para melhor ilustrac¸a˜o, 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˜o correta do 18, como vimos, e´ entre o 15 e o 23, isto e´, na sexta posic¸a˜o
do vetor. Significa que os elementos das posic¸o˜es 6 e 7 devem ser movidos um para
frente para abrir espac¸o no vetor para inserc¸a˜o do 18. Os elementos das posic¸o˜es 9
em diante na˜o va˜o mudar de lugar. Executando esta operac¸a˜o, e salvando o 18 em
alguma varia´vel tempora´ria, obteremos o seguinte vetor:
1 2 3 4 5