Ciências da computação dia 209

Hoje na aula de Ciências da computação, aprendemos sobre um dos algoritmos de ordenação mais fundamentais e intuitivos: o Insertion Sort (ordenação por inserção). O professor explicou que esse algoritmo é muito utilizado na prática para ordenar pequenas listas ou quando os dados já estão parcialmente ordenados. Vou compartilhar as anotações da aula, incluindo o passo a passo e o código que implementamos em Python.

O que é o Insertion Sort?

O Insertion Sort constrói a sequência ordenada final um elemento por vez. A cada iteração, um elemento da entrada é removido e inserido na posição correta na parte já ordenada do array. Essa abordagem é semelhante à maneira como organizamos cartas em um jogo de baralho: pegamos uma carta e a colocamos na posição adequada em relação às cartas já organizadas.

Como funciona o algoritmo?

O algoritmo percorre o array da esquerda para a direita. A partir do segundo elemento (índice 1), cada elemento é comparado com os elementos à sua esquerda (que já estão ordenados). Se o elemento da esquerda for maior, ele é deslocado uma posição para a direita. Esse deslocamento continua até encontrarmos a posição correta para inserir o elemento atual. O processo se repete até que todo o array esteja ordenado.

Uma característica importante é que o Insertion Sort é um algoritmo estável (elementos iguais mantêm a ordem relativa original) e in-place (não requer memória extra além do próprio array).

Exemplo passo a passo

Vamos ordenar o array [5, 2, 4, 6, 1, 3] utilizando o Insertion Sort:

• Iteração 1 (i=1, chave=2): Comparamos 2 com 5. Como 5 > 2, deslocamos 5 para a direita. Inserimos 2 na posição 0. Array: [2, 5, 4, 6, 1, 3]
• Iteração 2 (i=2, chave=4): Comparamos 4 com 5. 5 > 4, deslocamos 5. Comparamos 4 com 2 (posição 0). 2 < 4, então inserimos 4 na posição 1. Array: [2, 4, 5, 6, 1, 3]
• Iteração 3 (i=3, chave=6): 6 > 5, não há deslocamento. Array permanece: [2, 4, 5, 6, 1, 3]
• Iteração 4 (i=4, chave=1): Comparamos 1 com 6, 5, 4, 2. Todos são maiores, então deslocamos todos para a direita e inserimos 1 na posição 0. Array: [1, 2, 4, 5, 6, 3]
• Iteração 5 (i=5, chave=3): Comparamos 3 com 6,5,4. Deslocamos 6,5,4 para a direita. 3 é inserido entre 2 e 4. Array final: [1, 2, 3, 4, 5, 6]

Análise de complexidade

O Insertion Sort possui os seguintes tempos de execução:

• Melhor caso: O(n) — ocorre quando o array já está ordenado (apenas comparações, nenhum deslocamento).
• Pior caso: O(n²) — ocorre quando o array está ordenado inversamente (máximo de deslocamentos).
• Caso médio: O(n²) — para arrays aleatórios.

Por ser O(n²) no pior caso, ele não é adequado para grandes conjuntos de dados, mas é muito eficiente para listas pequenas ou quando a entrada já está quase ordenada.

Implementação em Python

Na aula, escrevemos a seguinte função para implementar o Insertion Sort:

def insertion_sort(arr):
    # Percorre o array a partir do segundo elemento
    for i in range(1, len(arr)):
        key = arr[i]  # elemento a ser inserido
        j = i - 1
        # Desloca os elementos maiores para a direita
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        # Insere a chave na posição correta
        arr[j + 1] = key
    return arr

Testamos com o array do exemplo e conferimos que o resultado é [1, 2, 3, 4, 5, 6]. O código é bem enxuto e pode ser reutilizado em projetos futuros.

Vantagens e desvantagens

Vantagens

• Simples de entender e implementar.
• Estável (mantém a ordem relativa de elementos iguais).
• Eficiente para arrays pequenos (tipicamente até 30-50 elementos).
• Adaptável: se o array já está quase ordenado, o desempenho é próximo de O(n).
• In-place: utiliza pouca memória extra.

Desvantagens

• Complexidade quadrática no pior caso, tornando-se lento para grandes conjuntos.
• Para listas grandes, algoritmos como Merge Sort, Quick Sort ou Heap Sort são mais adequados.

Perguntas frequentes (FAQ)

O Insertion Sort é estável?

Sim. O algoritmo insere o elemento na primeira posição onde ele é maior ou igual, portanto elementos iguais mantêm a ordem relativa original. Isso é importante em ordenações por múltiplos critérios.

Qual a diferença entre Insertion Sort e Selection Sort?

O Selection Sort encontra o menor elemento da parte não ordenada e o coloca no início, enquanto o Insertion Sort insere cada elemento na posição correta na parte ordenada. Na prática, o Insertion Sort costuma ser mais rápido que o Selection Sort para arrays pequenos, apesar de ambos terem complexidade O(n²).

Quando devo usar Insertion Sort no dia a dia?

É recomendado quando a lista é pequena (menos de 50 elementos) ou quando você sabe que os dados já estão parcialmente ordenados. Muitas implementações de algoritmos mais avançados (como Timsort, usado no Python) utilizam Insertion Sort como sub-rotina para ordenar pequenas partições.

Essa aula foi muito produtiva. O Insertion Sort é um ótimo exemplo de como um algoritmo simples pode ser útil em contextos específicos. Nos próximos dias vamos comparar outros métodos de ordenação e entender quando cada um é mais vantajoso. Até a próxima!