Insertion Sort
Constrói a lista ordenada um elemento por vez — como ordenar cartas de baralho na mão.
O(n²)O(1)Como Funciona
Passo a passo do algoritmo
Comece pelo segundo elemento
O primeiro elemento já está "ordenado" por definição. Pegue o segundo elemento e prepare para inseri-lo na posição correta da parte já ordenada.
para i de 1 até n-1: chave = array[i]Compare com os elementos à esquerda
Percorra de trás para frente a parte ordenada. Enquanto o elemento atual for maior que a chave, desloque-o uma posição para a direita.
j = i - 1
enquanto j >= 0 e array[j] > chave:
array[j+1] = array[j]
j--Insira na posição correta
Quando encontrar um elemento menor ou igual à chave (ou chegar ao início), a posição j+1 é onde a chave deve ser inserida.
array[j+1] = chaveParte esquerda sempre ordenada
Após inserir cada elemento, a parte à esquerda do índice atual sempre estará completamente ordenada. Repita para todos os elementos.
// array[0..i] está ordenado após cada iteraçãoImplementação
Código comentado em JavaScript e Python
function insertionSort(array) {
const n = array.length;
for (let i = 1; i < n; i++) {
const chave = array[i]; // Elemento a ser inserido
let j = i - 1;
// Desloca elementos maiores que 'chave' para a direita
while (j >= 0 && array[j] > chave) {
array[j + 1] = array[j]; // Desloca um elemento para direita
j--;
}
// Insere 'chave' na posição correta
array[j + 1] = chave;
}
return array;
}
// Exemplo de uso
const arr = [12, 11, 13, 5, 6];
console.log(insertionSort(arr)); // [5, 6, 11, 12, 13]Playground
Veja cada elemento sendo inserido na posição correta da parte ordenada
Quando Usar
Cenários ideais para este algoritmo
Listas pequenas
Overhead muito baixo torna o Insertion Sort mais rápido que algoritmos O(n log n) para arrays com menos de ~20 elementos.
Listas quase ordenadas
Extremamente eficiente quando a lista já está quase ordenada — cada elemento precisa de poucos deslocamentos.
Dados chegando em fluxo
Ideal para manter uma lista ordenada enquanto novos elementos chegam online, inserindo cada um na posição correta.
Base do Shell Sort
O Shell Sort é uma otimização do Insertion Sort com gaps maiores — entender o Insertion Sort é fundamental para o Shell Sort.
Complexidade
Análise de desempenho por cenário
| Cenário | Tempo |
|---|---|
| Melhor caso | O(n) |
| Caso médio | O(n²) |
| Pior caso | O(n²) |