Ordenação por seleção (selection sort) em Python
Nesta lição, você vai implementar o selection sort encontrando repetidamente o menor elemento e colocando-o na posição certa.
Introdução
O problema
Alguns algoritmos de ordenação tentam fazer o mínimo de movimentos possível, o que importa quando mover um item é caro. O selection sort mostra uma estratégia diferente do bubble sort: primeiro encontre o item certo, depois mova-o uma única vez.
Pense assim
O selection sort é como montar uma fila por altura. Você olha todos que ainda estão esperando, chama o mais baixo e o coloca no próximo lugar da fila. Depois olha de novo quem sobrou para achar o próximo mais baixo, até não sobrar ninguém.
for start in range(len(result)):📍 O próximo lugar livre na filaminimum = start🤔 Suponha que esta pessoa é a mais baixaresult[index] < result[minimum]🔎 Procure no resto alguém mais baixoresult[start], result[minimum] = ...🔄 Leve o mais baixo para o lugar livreO selection sort encontra várias vezes o menor item da parte não ordenada da lista e o troca para a próxima posição da parte ordenada. Ele faz O(n²) comparações, mas no máximo n - 1 trocas.
Pontos-chave
- Tudo à esquerda de
startjá está ordenado; tudo a partir destartainda não. minimumguarda o índice do menor valor encontrado até agora na parte não ordenada.- O laço interno
for index in range(start + 1, len(result)):percorre o resto da lista. result[start], result[minimum] = result[minimum], result[start]faz uma troca por posição.
Quando usar?
- Aprender e comparar estratégias de ordenação.
- Situações em que escrever ou mover itens é caro e comparar é barato.
- Encontrar os k menores itens parando depois de k passadas.
Quando não é preciso
- Programas reais:
sorted()é muito mais rápido. - Dados quase ordenados: o selection sort ainda olha tudo, enquanto o insertion sort termina rápido.
Visualizador de Ordenação por seleção (selection sort) em Python
O(n²)Use Executar ou Passo para acompanhar cada comparação e movimento dos dados.
Código de exemplo
def selection_sort(values):
result = values.copy()
for start in range(len(result)):
minimum = start
for index in range(start + 1, len(result)):
if result[index] < result[minimum]:
minimum = index
result[start], result[minimum] = result[minimum], result[start]
return result
print(selection_sort([64, 25, 12, 22, 11]))
Resultado da execução
[11, 12, 22, 25, 64]
Explicação do código
A variável minimum guarda a posição do menor valor no restante da lista. Ao final de cada passada, esse valor é trocado para a posição start. O algoritmo sempre tem complexidade O(n²) por causa das muitas comparações, mas faz no máximo n trocas.
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
Trocar dentro do laço interno
Isso o transforma em uma ordenação mais lenta e bagunçada, com muitas trocas.
for index in range(start + 1, len(result)):
if result[index] < result[start]:
result[start], result[index] = result[index], result[start]
for index in range(start + 1, len(result)):
if result[index] < result[minimum]:
minimum = index
result[start], result[minimum] = result[minimum], result[start]
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.
- Mínimo do Array Encontre o menor valor em uma lista. Fácil
- K-th Smallest Element Find the k-th smallest value without fully sorting. Médio