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.
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.
current = result[index]🃏 Pegue a próxima cartaresult[position] > current👈 A carta à esquerda é maior?result[position + 1] = result[position]➡️ Deslize a carta maior uma posição para a direitaresult[position + 1] = current📥 Coloque a carta no espaço vazioO 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
for index in range(1, len(result)):começa no segundo item; um único item já está ordenado.currentguarda o valor que está sendo inserido enquanto os maiores se movem.while position >= 0 and result[position] > current:desloca cada valor maior uma posição para a direita.result[position + 1] = currentcoloca 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.insortencontra 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
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]))
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.
- Teste com uma lista vazia, uma lista de um único elemento e uma lista com valores repetidos.
- Imprima o estado depois de cada passo para ver o algoritmo trabalhando.
- Meça o tempo com 100, 1.000 e 10.000 elementos e compare com outra solução.
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.
while position >= 0 and result[position] > current:
result[position + 1] = result[position]
result[position] = current
position -= 1
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