Algoritmos em Python

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.

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

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.

Da fila por altura ao código
for start in range(len(result)):📍 O próximo lugar livre na fila
minimum = start🤔 Suponha que esta pessoa é a mais baixa
result[index] < result[minimum]🔎 Procure no resto alguém mais baixo
result[start], result[minimum] = ...🔄 Leve o mais baixo para o lugar livre
Uma troca por posição, depois de olhar toda a parte não ordenada.
Em uma frase

O 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

  1. Tudo à esquerda de start já está ordenado; tudo a partir de start ainda não.
  2. minimum guarda o índice do menor valor encontrado até agora na parte não ordenada.
  3. O laço interno for index in range(start + 1, len(result)): percorre o resto da lista.
  4. 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

Executar código →
main.py
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]))
Gerar um botão Run para este exemplo

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.

  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

Trocar dentro do laço interno

Isso o transforma em uma ordenação mais lenta e bagunçada, com muitas trocas.

Problema
for index in range(start + 1, len(result)):
    if result[index] < result[start]:
        result[start], result[index] = result[index], result[start]
Correção
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.

Todos os desafios