Site do Fundão: Algoritmo Insertion Sort

O Insertion Sort é um algoritmo eficiente para ordenar um pequeno número de elementos. Basicamente, este algoritmo varre um array de elementos da esquerda para a direita e a medida que avança vai deixando os elementos mais a esquerda ordenados.

Algoritmo: Insertion Sort

   para j = 2 até tamanho[array] faça
      chave = array[j];
      i = j - 1;
      // Ordenando os elementos mais a esquerda
      enquanto i > 0 e array[i] > chave faça
         array[i+1] = array[i];
         i = i -1;			
      fim enquanto
      array[i+1] = chave;
   fim para

Obs.: Para colocar em ordem decrescente experimente trocar o sinal de maior pelo sinal de menor dentro do laço mais interno.

O tempo gasto para executar o algoritmo do Insertion Sort depende do valor de entrada. Ordenar milhares de números leva bem mais tempo do que ordenar três números. Além disso, o Insertion Sort pode levar diferentes quantidades de tempo para ordenar duas sequências de entrada de mesmo tamanho dependendo do quanto elas já estão ordenadas.

O melhor caso para o Insertion Sort é quando o array já está ordenado. Neste caso a comparação no laço interno sempre falhará na primeira comparação e o tempo de execução dependerá apenas do laço externo. O tempo de execução obdecerá uma função linear e a complexidade do algoritmo será de O(n).

O pior caso é quando o array está na ordem inversa. Nesta situação para cada iteração do laço externo, o laço interno executará n-1 vezes, onde n é o valor da variável j no laço externo. Temos que a complexidade de tempo do algoritmo neste caso será de O(n(n-1)) = O(n²-n) = O(n²).