Código fonte Insertion Sort

InsertionSort

Sua teoria baseia-se em ordenar os valores da esquerda para a direita, deixando os elementos lidos (a esquerda) ordenados. Este é geralmente utilizado para ordenar um pequeno número de valores, onde faz-se muito eficiente. A complexidade do código é:

Complexidade Pior Caso: O(n²)

Complexidade Caso Médio: O(n²)

Complexidade Melhor Caso: O(n)

Quando temos um caso onde a complexidade é n² devemos evitar, visto que a redução de desempenho deste algoritmo é exponencial. Porém, no seu melhor caso temos uma constante n que significa a inalteração da velocidade, proporcional à quantidade de elementos.

Lembre-se que estamos trabalhando com proporcionalidade, então dizer que não varia não significa que um vetor de 10 elementos será ordenado na mesma velocidade de um vetor de um milhão de elementos, mesmo no melhor caso, porém a proporcionalidade entre a quantidade de elementos e sua velocidade continua constante, diferente do Pior Caso que aumenta ao quadrado.

O melhor caso ocorre quando todos os elementos já estão ordenados e o pior caso é exatamente o contrário, quando todos os elementos estão desordenados. Vejamos um exemplo para entender melhor essa teoria na Listagem 1.

Listagem 1. Aplicando InsertionSort

public static void main(String[] args) throws IOException {

int quantidade = 10000;

int[] vetor = new int[quantidade];

for (int i = 0; i < vetor.length; i++) {

vetor[i] = (int) (Math.random()*quantidade);

}

long tempoInicial = System.currentTimeMillis();

insertionSort(vetor);

long tempoFinal = System.currentTimeMillis();

System.out.println("Executado em = " + (tempoFinal - tempoInicial) + " ms");

}

public static void insertionSort(int[] vetor) {

int j;

int key;

int i;

for (j = 1; j < vetor.length; j++)

{

key = vetor[j];

for (i = j - 1; (i >= 0) && (vetor[i] > key); i--)

{

vetor[i + 1] = vetor[i];

}

vetor[i + 1] = key;

}

}

O primeiro passo é entender o funcionamento do método insertionSort(). Este irá percorrer todo o vetor começando do segundo elemento e atribuindo o mesmo a uma variável chamada key.

O algoritmo começa fazendo uma iteração em todos os elementos do vetor, a partir do segundo elemento, por isso “j=1” e não “j=0”.

A variável “key” armazena inicialmente o primeiro valor lido pelo laço for, que no caso será o segundo elemento do vetor. O segundo laço itera sobre os valores que estão antes da variável “key”:

key = vetor[j];

for (i = j - 1; (i >= 0) && (vetor[i] >