Algoritmos em Python

Ordenação por inserção (insertion sort) em Python

Nesta lição, você vai implementar o insertion sort inserindo cada elemento na posição correta da parte já ordenada.

  • Intermediário
  • 2 min de leitura
  • 1 exemplo executável

Introdução

O problema

Os dados muitas vezes chegam quase ordenados, ou um item por vez: uma lista ordenada de pontuações ganha uma nova pontuação. Reordenar tudo é desperdício. O insertion sort lida muito bem com esse caso e é como muita gente ordena cartas na mão.

Pense assim

O insertion sort é como você ordena as cartas na mão. Você pega uma carta por vez e a desliza para a esquerda, passando por todas as cartas maiores, até ela ficar no lugar certo. As cartas à esquerda estão sempre em ordem.

Das cartas ao código
current = result[index]🃏 Pegue a próxima carta
result[position] > current👈 A carta à esquerda é maior?
result[position + 1] = result[position]➡️ Deslize a carta maior uma posição para a direita
result[position + 1] = current📥 Coloque a carta no espaço vazio
A parte da esquerda está sempre ordenada; cada novo item é inserido nela.
Em uma frase

O insertion sort monta uma parte ordenada um item por vez, deslocando os itens maiores para a direita e inserindo o item atual no espaço aberto. No pior caso é O(n²), mas em dados quase ordenados fica perto de O(n).

Pontos-chave

  1. for index in range(1, len(result)): começa no segundo item; um único item já está ordenado.
  2. current guarda o valor que está sendo inserido enquanto os maiores se movem.
  3. while position >= 0 and result[position] > current: desloca cada valor maior uma posição para a direita.
  4. result[position + 1] = current coloca o valor no espaço que foi aberto.

Quando usar?

  • Listas pequenas ou quase ordenadas.
  • Manter uma lista ordenada à medida que chegam novos itens.
  • Como passo final dentro de ordenações mais rápidas, que passam para o insertion sort em pedaços pequenos.

Quando não é preciso

  • Listas grandes e aleatórias: os deslocamentos ficam lentos, então use sorted().
  • Inserir com frequência em uma lista ordenada grande: bisect.insort encontra a posição com busca binária.

Visualizador de Ordenação por inserção (insertion sort) em Python

O(n²)

Use Executar ou Passo para acompanhar cada comparação e movimento dos dados.

Código de exemplo

Executar código →
main.py
def insertion_sort(values):
    result = values.copy()
    for index in range(1, len(result)):
        current = result[index]
        position = index - 1
        while position >= 0 and result[position] > current:
            result[position + 1] = result[position]
            position -= 1
        result[position + 1] = current
    return result

print(insertion_sort([9, 5, 1, 4, 3]))
Gerar um botão Run para este exemplo

Resultado da execução

[1, 3, 4, 5, 9]

Explicação do código

A variável current guarda o valor que precisa ser inserido. O laço while desloca uma posição para a direita os valores maiores que current, abrindo espaço, e então current é colocado nesse lugar. No pior caso, a complexidade é O(n²), mas com dados quase ordenados o algoritmo chega perto de O(n).

Altere os valores e execute o programa no compilador Python online CodeUtility sem instalar Python.

Exercícios práticos

Tente modificar o código seguindo as sugestões abaixo. Mudar o código e observar o resultado ajuda você a entender muito mais do que só ler.

  1. Teste com uma lista vazia, uma lista de um único elemento e uma lista com valores repetidos.
  2. Imprima o estado depois de cada passo para ver o algoritmo trabalhando.
  3. Meça o tempo com 100, 1.000 e 10.000 elementos e compare com outra solução.
Executar no compilador Python →

Erros comuns

Escrever current de volta dentro do laço

O valor deve ser colocado uma vez só, depois que todos os maiores se moveram.

Problema
while position >= 0 and result[position] > current:
    result[position + 1] = result[position]
    result[position] = current
    position -= 1
Correção
while position >= 0 and result[position] > current:
    result[position + 1] = result[position]
    position -= 1
result[position + 1] = current

Terminou esta lição?

Marque como aprendida para acompanhar seu progresso.

Pratique com um desafio

Use o conteúdo desta lição para resolver um problema real. Cada desafio roda no navegador, com testes instantâneos e uma revisão por IA.

Todos os desafios