Particionando em pares e ímpares

Agora, vamos utilizar indução para resolver um problema fácil, que com indução ficou mais fácil ainda.

Problema:

• Dada uma sequência de n valores inteiros, rearranjar os elementos de forma que os valores pares apareçam antes dos ímpares.

Idéia indutiva:

• Caso Base: uma lista com 1 elemento já está particionada em pares e ímpares.
• Hipótese de Indução: podemos assumir que o problema já foi resolvido para n-1 elementos, e que sabemos onde termina a lista de pares.
• Caso Geral: basta verificar se o último elemento é par ou ímpar, se ele for par basta inseri-lo no final da lista de pares, caso contrário, não fazemos nada.  

Agora, vamos ilustrar o problema com um exemplo:

• Situação inicial: Um vetor com valores pares e ímpares misturados.

• Hipótese de indução: agora vamos "imaginar" que o problema já foi resolvido para os primeiros n - 1 elementos, e que sabemos onde termina a lista de pares.

• Caso Geral: Pronto! Agora ficou muito fácil, podemos perceber que o último elemento é par, então vamos incrementar o final da lista de pares e trocar o último  elemento da lista de pares com o último elemento do vetor.

• E assim chegamos a solução do problema.

O algoritmo segue exatamente a idéia apresentada acima. Vamos assumir que o problema já foi resolvido para os primeiros n - 1 elementos, e dentro do loop só escreveremos código para trocar o último elemento do vetor (caso ele seja par) com o último elemento da lista de pares. E não podemos esquecer do caso base!

• Implementação em C++ (versão iterativa)

fimPares = -1; // caso base
for(int i = 0; i < tamVetor; i++)
  if(vetor[i] % 2 == 0){  // passo indutivo
    fimPares++;
    troca(vetor[i], vetor[fimPares]);
  }

Complexidade do algoritmo: A relação de recorrência da nossa solução é T(n) = T(n - 1) + 1, ou seja, o tempo gasto pela hipótese de indução para separar os n - 1 elementos mais o tempo gasto para colocar o último elemento no final da lista de pares. Derivando T(n) temos:

$T(n) = T(n - 1) + 1$
$T(n) = T(n - 2) + 1 + 1$
$T(n) = T(n - 3) + 1 + 1 + 1$
$T(n) = T(n - 4) + 1 + 1 +1 +1$
...
$T(n) = 1 + 1 + 1 + 1 + 1 + 1 + ... + 1 + 1$
$T(n) = O(n)$

Logo, concluímos que o nossa solução tem complexidade linear.