Imagine que você está empilhando livros em ordem de tamanho, do maior para o menor. Cada vez que pega um livro, você compara com os outros na pilha e o coloca no lugar certo, reorganizando se precisar, até que a pilha inteira esteja na ordem correta.

Teoria

Quando você pega o primeiro livro e o coloca na prateleira. Como é o único, ele já está organizado, por esse motivo, começamos a comparar os itens do nosso array a começar pelo índice 1.

A ideia é percorrer os itens do array, começando pela posição inicial e movendo para a esquerda. Primeiro, comparamos o item na posição inicial com o da posição anterior, se for maior, trocamos suas posições.

Isto é feito até que a posição inicial chegue ao último item do array, no caso, posição inicial = índice 5 ou até que a posição inicial tenha um valor maior que a posição anterior.

Prática

Abaixo, você encontrará um exemplo prático do algoritmo de ordenação por inserção em JavaScript.

function insertionSort(array) 
function insertionSort(array) {
    for (let posicaoInicial = 1; posicaoInicial < array.length; posicaoInicial++) {
        // Seleciona o elemento atual
        let elementoAtual = array[posicaoInicial];
        let posicao = posicaoInicial - 1; // Índice do elemento anterior

        // Move os elementos maiores para frente
        while (posicao >= 0 && array[posicao] > elementoAtual) {
            array[posicao + 1] = array[posicao];
            posicao--;
        }

        // Insere o elemento atual na posição correta
        array[posicao + 1] = elementoAtual;
    }
    return array;
}

// Exemplo de uso
const numbers = [5, 3, 8, 6, 2];
console.log("Antes da ordenação:", numbers);
console.log("Depois da ordenação:", insertionSort([...numbers]));

Complexidade de algoritmo

MELHOR CENÁRIO: O(N)

Ocorre quando o array já está ordenado. Nesse caso, o laço interno não precisa realizar deslocamentos, apenas compara os elementos adjacentes e avança.

PIOR CASO: O(N²)

Ocorre quando o array está ordenado em ordem inversa. Nesse cenário, cada elemento precisa ser comparado e deslocado até o início da lista, resultando em um número quadrático de operações.

CASO MÉDIO: O(N²)

Mesmo em casos aleatórios, o número médio de deslocamentos e comparações é proporcional a n², pois o laço interno ainda é executado várias vezes para cada elemento.

Complexidade de espaço: O(1)

O Insertion Sort é um algoritmo in-place, ou seja, ele não requer espaço adicional significativo além do necessário para armazenar os dados.

Quando utilizar

Listas Pequenas

Quando o número de elementos é pequeno (menor que 20), o Overhead de algoritmos mais complexos como Quick Sort ou Merge Sort pode não compensar, e o Insertion Sort tem desempenho aceitável.

Listas quase ordenadas

Se a lista já está quase ordenada ou possui apenas alguns elementos fora de ordem, o Insertion Sort pode ordená-la rapidamente em tempo quase linear.

Sistemas com pouca memória

O algoritmo é in-place, ou seja, não usa memória extra significativa além da entrada.

Dados em tempo real

Quando os elementos chegam dinamicamente e precisam ser ordenados à medida que chegam, o Insertion Sort pode ser usado para inserir o novo elemento na posição correta.

Insertion Sort