Insertion Sort

Insertion Sort
O método de ordenação por inserção é o mais rápido entre os métodos básicos(método das bolhas, método de seleção direta e método de ordenação por inserção).
A principal característica deste método consiste em ordenar um conjunto de elementos, utilizando um subconjunto ordenado localizado em seu inicio, e em cada interação, acrescentamos a este subconjunto mais um elemento, até que atingimos o último elemento do conjunto assim com que ele se torne ordenado.

Método
Este método, considera-se o array(vetor) a ordenar como um array dividido em dois subarrays (esquerdo e direito), com o da esquerda ordenado e o da direita desordenado. Os elementos são retirados um de cada vez do sub-array da direita (não ordenado), e move-se esse elemento para o sub-array da esquerda, inserindo-o na posição correta por forma a manter o sub -array da esquerda ordenado, terminando o processo quando o sub-array da direita ficar vazio.

Desempenho
O tempo é proporcional ao número de execuções da comparação "v[i] > x". O número de execuções da comparação "v[i] > x" no pior caso é igual à soma da última coluna da tabela, ou seja n (n-1) / 2 j i

Números de valores de i

1

0

1

2

1, 0

2

3

2, 1, 0

3

...

...

...

n-1

n-2, n-3, …, 1, 0

n-1

Desempenho
Esse número cresce como n2. O algoritmo é um tanto lento: se a ordenação de n números leva t segundos então a ordenação de 2n números levará 4t segundos e a ordenação de 10n números consumirá 100t segundos!

Desempenho
O tempo é proporcional ao número de execuções da comparação "v[i] > x". O número de execuções da comparação "v[i] > x" no pior caso é igual à soma da última coluna da tabela, ou seja

n (n-1) / 2

Algoritmo void insertionSort (int vet[], int tamanho){ int i, j, tmp; for (i = 1; i < tamanho; i++) { j = i; while (j > 0 && vet[j - 1] > vet[j]) { tmp = vet[j]; vet[j] = vet[j - 1]; vet[j - 1] = tmp; j--; }
}
}