O Insertion Sort, ou ordenação por inserção, funciona como organizar cartas na mão: pega o próximo elemento e o desliza para a esquerda até encontrar o lugar certo dentro da parte já ordenada.
Como o Insertion Sort Funciona
- Considere o 1º elemento como uma parte ordenada de tamanho 1.
- Pegue o próximo elemento.
- Compare com os elementos da parte ordenada, da direita para a esquerda.
- Desloque os maiores uma posição para a direita e insira o elemento no espaço aberto.
- Repita até o último elemento.
Complexidade do Insertion Sort
| Melhor caso | Caso médio | Pior caso | Memória extra | Estável? |
|---|---|---|---|---|
| O(n) | O(n²) | O(n²) | O(1) | Sim |
Quando usar
Vetores pequenos (até umas dezenas de elementos) e vetores quase ordenados. Por isso algoritmos híbridos como o Timsort (Python e Java) e o Introsort (C++) usam Insertion Sort nos pedaços pequenos.
Insertion Sort em C
void insertion_sort(int v[], int n) {
for (int i = 1; i < n; i++) {
int chave = v[i];
int j = i - 1;
while (j >= 0 && v[j] > chave) {
v[j + 1] = v[j];
j--;
}
v[j + 1] = chave;
}
}Insertion Sort em Python
def insertion_sort(v):
for i in range(1, len(v)):
chave = v[i]
j = i - 1
while j >= 0 and v[j] > chave:
v[j + 1] = v[j]
j -= 1
v[j + 1] = chave
return vInsertion Sort em Java
static void insertionSort(int[] v) {
for (int i = 1; i < v.length; i++) {
int chave = v[i];
int j = i - 1;
while (j >= 0 && v[j] > chave) {
v[j + 1] = v[j];
j--;
}
v[j + 1] = chave;
}
}Quer comparar com outros métodos? No visualizador de algoritmos de ordenação você roda todos no mesmo vetor e compara o número de comparações e trocas.
Perguntas Frequentes
Qual a complexidade do Insertion Sort?
O(n²) no caso médio e no pior caso (vetor invertido). No melhor caso, com o vetor já ordenado, é O(n): cada elemento é comparado uma única vez.
O Insertion Sort é estável?
Sim. Ele só desloca elementos estritamente maiores que a chave, então elementos iguais mantêm a ordem original.
Por que o Insertion Sort é usado em algoritmos profissionais?
Porque, para vetores pequenos, sua constante é muito baixa e ele aproveita a ordem que já existe. O Timsort, padrão do Python e do Java para objetos, ordena pequenos trechos com Insertion Sort e depois os intercala.