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