Insertion-Sort: Uma descrição Indutiva

Agora vamos fazer uma descrição indutiva do algoritmo Insertion-Sort. É importante lembrar que este tipo de abordagem é um pouco diferente dos métodos convencionais que muitos livros utilizam. No entanto, de forma simples e clara resolveremos o problema de ordenação.

Idéia indutiva:

• Caso Base: é trivial, pois uma lista com apenas um elemento já está ordenada.
• Hipótese de Indução: vamos assumir que a lista com n- 1 elementos já está ordenada.
• Caso Geral: agora, basta inserir o último elemento na sequência que, por hipótese de indução, já está ordenada.

Antes de derivar o algoritmo vamos visualizar um exemplo.

Situação inicial: Vetor desordenado

Agora vamos trabalhar com os primeiros n - 1 elementos

Vamos assumir que os n - 1 elementos já estão ordenados

Agora, só precisamos inserir o último elemento na sequência ordenada

E vamos mais uma vez, construir o nosso algoritmo seguindo a idéia indutiva apresentada acima.

• Implementação em Python (versão recursiva)

def ins_sort_rec(seq, i):
 if i==0: return
 ins_sort_rec(seq, i-1)
 j = i
 while j > 0 and seq[j-1] > seq[j]:
  seq[j-1], seq[j] = seq[j], seq[j-1]
  j -= 1

• Implementação em Java (versão interativa)

static void insertionSort(int vet[]){
  int i, aux;
  for(int j = 1; j < vet.length; j++){
    i = j - 1;
    aux = vet[j];
    while(i > -1 && vet[i] > aux){
      vet[i+1] = vet[i];
      i--;
    }
    vet[i + 1] = aux;
  }
}

Complexidade do algoritmo
A relação de recorrência que expressa a complexidade de tempo do insertion-sort é: T(n) = T(n - 1) + n.
Essa relação nos diz que o tempo do insertion-sort é igual ao tempo que a hipótese de indução gasta para ordenar os n - 1 elementos, mais o tempo gasto para inserir um elemento na sequência ordenada.
Resolvendo a recorrência temos:

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

Ou seja, a complexidade de tempo do insertion-sort é limitada pela função quadrática.