Parte II: Recursão

Algoritmos de Ordenação

Nesse capítulo serão apresentados dois algoritmos de ordenação, isto é, algoritmos que recebem como entrada um array de números (ou de "character") e retorna outro array, com os mesmos elementos do array de entrada, só que em ordem crescente. Veja que isso nada mais é do que a implementação da função já pronta no R.

Existem vários algoritmos de ordenação, uns mais eficientes que os outros. Mas vamos nos concentrar em dois métodos: O método de Ordenação Bolha (Bubble Sort) e o método de Ordenação Rápida (Quick Sort).

Ordenação Bolha (Bubble Sort)

A ideia desse método é ordenar o vetor seguindo os seguintes passos:

  • Primeiro leve o maior elemento para a última posição, comparando os elementos dois a dois até a última posição;
  • Depois repita o processo e levar o segundo maior elemento para a segunda maior posição, comparando os elementos dois a dois até a penúltima posição;
  • Esse processo se repete várias vezes até que o vetor esteja todo ordenado.

Suponha \(v = (37,33,48,12,92,25,86,57)\) o vetor de entrada, ou seja, o vetor que queremos ordenar. O primeiro passo é levar o maior elementos para a maior posição fazendo comparações de elementos dois a dois.

v1 v2 v3 v4 v5 v6 v7 v8 comentários
37 33 48 12 92 25 86 57 como 37>33, troca
33 37 48 12 92 25 86 57 como 37<48, não troca
33 37 48 12 92 25 86 57 como 48>12, troca
33 37 12 48 92 25 86 57 como 48<92, não troca
33 37 12 48 92 25 86 57 como 92>25, troca
33 37 12 48 25 92 86 57 como 92>86, troca
33 37 12 48 25 86 92 57 como 92>57, troca
33 37 12 48 25 86 57 92 fim dessa etapa.

Veja que para realizar essa etapa foram necessárias 7 comparações. Agora que o maior elemento já está na última posição o próximo passo é levar o segundo maior elemento até a segunda maior posição. Repare que nesse caso as comparações serão até a penúltima posição, uma vez que a última posição já está com o seu devido elemento.

v1 v2 v3 v4 v5 v6 v7 v8 comentários
33 37 12 48 25 86 57 92 como 33<37, não troca
33 37 12 48 25 86 57 92 como 37>12, troca
33 12 37 48 25 86 57 92 como 37<48, não troca
33 12 37 48 25 86 57 92 como 48>25, troca
33 12 37 25 48 86 57 92 como 48<86, não troca
33 12 37 25 48 86 57 92 como 86>57, troca
33 12 37 25 48 57 86 92 fim dessa etapa.

Veja que para realizar essa etapa foram necessárias 6 comparações. Agora o terceiro maior elementos será levado para a terceira maior posição.

v1 v2 v3 v4 v5 v6 v7 v8 comentários
33 12 37 25 48 57 86 92 como 33>12, troca
12 33 37 25 48 57 86 92 como 33<37, não troca
12 33 37 25 48 57 86 92 como 37>25, troca
12 33 25 37 48 57 86 92 como 37<48, não troca
12 33 25 37 48 57 86 92 como 48<57, não troca
12 33 25 37 48 57 86 92 fim dessa etapa.

Veja que para realizar essa etapa foram necessárias 5 comparações. Agora o quarto maior elementos será levado para a quarta maior posição.

v1 v2 v3 v4 v5 v6 v7 v8 comentários
12 33 25 37 48 57 86 92 como 12<33, não troca
12 33 25 37 48 57 86 92 como 33>25, troca
12 25 33 37 48 57 86 92 como 33<37, não troca
12 25 33 37 48 57 86 92 como 37<48, não troca
12 25 33 37 48 57 86 92 fim dessa etapa.

Veja que para realizar essa etapa foram necessárias 4 comparações.

Nesse momento o vetor já está ordenado, porém o computador não tem como saber disso. Por isso as etapas seguintes serão realizadas, apesar de nenhuma troca ser feita.

Algumas observações sobre o método e o sobre exemplo acima.

  • Em um vetor de tamanho \(n\) é preciso de \(n-1\) comparações para realizar a primeira etapa, isto é, levar o maior elemento para a maior posição.
  • Já para levar o segundo maior elemento para a segunda maior posição são realizadas \(n-2\) comparações.
  • De forma geral, para levar o \(j\)-ésimo maior elemento para a \(j\)-ésima maior posição, isto é realizar a etapa \(j\), são realizadas \(n-j\) comparações.
  • Em cada etapa \(j\) serão comparados os elementos das posições \(i\) e \(i+1\) para \(i=1, \ldots, n-j\).
  • De forma geral, para ordenar um vetor de tamanho \(n\) são realizadas \(n-1\) etapas.

Agora pensando no peseudocodigo, veja que serão necessários dois laços (loops), um dentro do outro. Um para controlar as etapas e outro para controlar as comparações dentro de cada etapa. Veja primeiro um pseudocódigo não recursivo para o algoritmo apresentado.

Entrada: \(v\)

Saída: vetor com os elementos de \(v\) ordenados em ordem crescente.

Nome: OrdenaBolha

1. Defina n = tamanho do vetor v;
2. Inicie j = 1;
3. Inicie i = 1;
4. Se v[i] > v[i+1], troque a posição i com posição i+1 no vetor v; (ATENÇÃO!)
5. Incremente: i = i + 1;
6. Se i <= n-j, volte para a linha 4;
7. Incremente: j = j + 1;
8. Se j <= n-1, volte para a linha 3; 
9. Retorne v.

Veja que a variável \(j\) controla as etapas, por isso ela varia de \(1\) até \(n-1\). Já a variável \(i\) controla as comparações dentro de cada etapa \(j\), por isso ela varia de \(1\) até \(n-j\).

Atenção: Na linha 4 o elemento da posição \(i\) será trocado com o elemento da posição \(i+1\). Para isso é necessário utilizar uma variável temporária, senão um dos elementos do vetor será perdido.

No R a troca dos elementos entre as posições \(i\) e \(i+1\) pode ser feita da seguinte maneira:

temp <- v[i]
v[i] <- v[i+1]
v[i+1] <- temp

Agora o pseudocódigo do algoritmo recursivo.

Entrada: \(v\)

Saída: vetor com os elementos de \(v\) ordenados em ordem crescente.

Nome: OrdenaBolhaRec

1. Defina n = tamanho do vetor v;
2. Se n=1, retorne v;
3. Inicie i = 1;
4. Se v[i] > v[i+1], troque a posição i com posição i+1 no vetor v; (ATENÇÃO!)
5. Incremente: i = i + 1;
6. Se i <= n-1, volte para a linha 4;
7. Defina w = v[1:(n-1)];
8. Defina wo = OrdenaBolhaRec(w);
9. Retorne vo = (wo,v[n]).

Veja que entre as linhas 2 e 6 o que está sendo feito é levar o maior elemento para a maior posição. Dessa forma o vetor \(w\) será formado pelos elementos do vetor \(v\) a menos do maior deles, que agora está na posição de índice \(n\). Dessa forma \(wo\) guarda os elementos de \(v\), a menos do maior deles, já em ordem crescente. Então \(v\) em ordem crescente será definido pela concatenação entre os elementos em \(wo\) e o maior elementos de \(v\), que está guardado em \(v_n\).

Ordenação Rápida (Quick Sort)

Nessa seção será visto outro algoritmo para ordenação de vetores. É uma opção que realiza menos comparações em média, mas é também de mais difícil compreensão. A ideia desse método é ordenar o vetor da seguinte maneira:

  • Primeiro o valor guardado na primeira posição, chamado de pivô, será levado para a sua posição correta de forma que os elementos à esquerda são menores que o pivô e os elementos à direita são maiores que o pivô.
  • O passo seguinte é repetir o mesmo processo no sub-vetor à esquerda e no sub-vetor à diretia do pivô.

A questão principal é: como se leva o pivô para a sua posição correta? Já essa tarefa será feita da seguinte maneira:

  • Primeiro percorra o vetor a partir da posição seguinte a do pivô até encontrar um elemento maior que o pivô. Seja \(i\) a posição desse elemento.
  • Se não existir elemento maior que o pivô, a posição correta do pivô é a última e FIM.
  • Caso exista, percorra o vetor do final para o início até encontrar um elemento menor ou igual ao pivô. Seja \(j\) a posição desse elemento.
  • Se \(i < j\), troque os elementos das posições \(i\) e \(j\) e recomece a busca por novos \(i\) e \(j\) a partir das posições trocadas.
  • Se \(i > j\), a posição correta para o pivô é a posição \(j\).

Vejamos como o mesmo vetor \(v\) será ordenado pelo método de Ordenação Rápida.

v1 v2 v3 v4 v5 v6 v7 v8 comentários
37 33 48 12 92 25 86 57 pivo = 37, \(i \neq 2\)
37 33 48 12 92 25 86 57 \(i=3\)
37 33 48 12 92 25 86 57 \(j \neq 8\)
37 33 48 12 92 25 86 57 \(j \neq 7\)
37 33 48 12 92 25 86 57 \(j = 6\)
37 33 25 12 92 48 86 57 como \(i<j\), troca v3 com v6
37 33 25 12 92 48 86 57 \(i \neq 4\)
37 33 25 12 92 48 86 57 \(i = 5\)
37 33 25 12 92 48 86 57 \(j \neq 5\)
37 33 25 12 92 48 86 57 \(j = 4\)
12 33 25 37 92 48 86 57 como \(i>j\), troca pivo com v4

Veja que depois desses passos o pivô está em sua posição correta uma vez que antes dele estão os elementos menores que ele e depois os maiores. Agora o algoritmo é repetido para o sub-vetor à esquerda do pivo.

v1 v2 v3 comentários
12 33 25 pivo = 12, \(i = 2\)
12 33 25 \(j \neq 3\)
12 33 25 \(j \neq 2\)
12 33 25 \(j = 1\)
12 33 25 como \(i>j\), troca pivo com v1

Teoricamente o processo seria refeito no sub-vetor a esquerda do pivô 12, mas como não existe vamos para o subvetor à direita do pivô 12.

v1 v2 comentários
33 25 pivo = 33, \(i \neq 2\)
25 33 não existe \(i\), pivo vai pra última posição

Juntando o resultado do subvetor à esquerda do primeiro pivô, o 37, já temos um pedaço ordenado: (12, 25, 33, 37). Vamos agora trabalhar com o subvetor à direita do pivô 37.

v1 v2 v3 v4 comentários
92 48 86 57 pivo = 92, \(i \neq 2\)
92 48 86 57 \(i \neq 3\)
92 48 86 57 \(i \neq 4\)
57 48 86 92 não existe \(i\), pivo vai pra última posição

Repetir o processo no subvetor à esquerda do 92.

v1 v2 v3 comentários
57 48 86 pivo = 57, \(i \neq 2\)
57 48 86 \(i = 3\)
57 48 86 \(j \neq 3\)
57 48 86 \(j = 2\)
48 57 86 como \(i>j\), troca pivo com v2

Nesse próximo passo o processo seria aplicado nos subvetores à esquerda e a direita do 57. Mas com tamanho 1 a ordenação é imediata, retorna o próprio vetor de entrada.

Percebeu que o vetor foi ordenado? Juntando tudo: (12, 25, 33, 37, 48, 57, 86, 92).

Reparou que a ideia do algoritmo é recursiva? Caso básico: se \(n=1\) retorna o próprio vetor de entrada. Se não, primeiro coloque o pivô na posição correta, como explicado acima. Em seguida defina \(we\) e \(wd\) como os subvetores à esquerda e à direita e aplique a ordenação rápida em cada um deles. O vetor ordenado será a concatenação entre \(we\) ordenado, o pivô e \(wd\) ordenado. Veja o pseudocódigo.

Entrada: \(v\)

Saída: vetor com os elementos de \(v\) ordenados em ordem crescente.

Nome: OrdenaRapidoRec

1. Defina n = tamanho do vetor v;
2. Se n=1, retorne v;
3. Defina pivo = v[1], i = 2 e j=n;
4. Se v[i] <= pivo e i < n, faça i = i + 1 e repete a linha 4;
5. Se i = n e v[i] <= pivo: troca o pivo com v[n]; defina w=v[1:(n-1)]; wo = OrdenaRapidoRec(w) e retorna c(wo,pivo).
6. Se v[j] > pivo, faça j = j - 1 e repete a linha 6. 
7. Se j = 1: defina w=v[2:n]; wo = OrdenaRapidoRec(w) e retorna c(pivo,wo).
8. Se j < i: troca o v[j] com o pivo; defina we=v[1:(j-1)]; wd=v[j+1,n]; weo = OrdenaRapidoRec(we); wdo = OrdenaRapidoRec(wd); retorne c(weo,pivo,wdo).
9. Se i < j, troca o v[i] com o v[j] e volte para a linha 4;

Como esse não é um algoritmo fácil de ser implementado, mesmo com o pseudocódigo, segue o código em R para a função OrdenaRapidoRec. Só uma última observação, essa função ficaria complicada de mais de forma não recursiva.

OrdenaRapidoRec = function(v){
  n = length(v)
  
  if(n==1)
    return(v)
  
  pivo = v[1]
  
  i = 1
  j = n
  
  repeat{
    #busca do i
    while(v[i] <= pivo && i < n){
      i = i + 1
    }
    
    if(i == n &&  v[i] <= pivo){ #nao encontramos i tal que v[i]>pivo
      #troca o pivo com v[n]
      v[1] = v[n]
      v[n] = pivo
      
      w=v[1:(n-1)]
      wo = OrdenaRapidoRec(w)
      return(c(wo,pivo))
    }
    
    #busca do j
    while(v[j] > pivo){
      j = j - 1
    }
    
    if(j == 1){
      
      w=v[2:n]
      wo = OrdenaRapidoRec(w)
      return(c(pivo,wo))
    }
    
    if(j < i){
      #troca o v[j] com o pivo
      v[1] = v[j]
      v[j] = pivo
      
      we=v[1:(j-1)]
      wd=v[(j+1):n]
      weo = OrdenaRapidoRec(we)
      wdo = OrdenaRapidoRec(wd)
      
      return(c(weo,pivo,wdo))
    }
    
    #troca o v[i] com o v[j]
    aux = v[i]
    v[i] = v[j]
    v[j] = aux
    
  }
}

OrdenaRapidoRec(c(9,7,4,1,2,8,3,5,6))
## [1] 1 2 3 4 5 6 7 8 9