Entenda o que é Selection Sort, como o algoritmo seleciona o menor valor, veja um exemplo passo a passo e conheça sua complexidade.
Em resumo:
Selection Sort é um algoritmo de ordenação que organiza uma lista escolhendo, a cada etapa, o menor valor ainda não ordenado e colocando-o na posição correta, da esquerda para a direita.
Esse processo se repete até que todos os elementos estejam na ordem crescente, sem exigir estruturas de dados adicionais além da própria lista.
O algoritmo é frequentemente usado como primeiro contato com lógica de ordenação por ser simples de visualizar: a cada rodada, uma “varredura” identifica o menor valor restante e o leva para a posição seguinte da sequência já ordenada.
O funcionamento do Selection Sort segue uma lógica fixa: para cada posição da lista, o algoritmo percorre todos os valores restantes à procura do menor. Essa posição avança uma casa a cada rodada, reduzindo o trecho ainda não ordenado.
Durante a varredura, o algoritmo não troca valores imediatamente ao encontrar um número menor. Em vez disso, ele guarda a posição (o índice) do menor valor encontrado até aquele ponto e só realiza a troca depois de examinar todos os elementos restantes naquela rodada.
Considere a lista hipotética [5, 2, 8, 1] como exemplo ilustrativo de como o algoritmo se comporta. Na primeira rodada, o algoritmo percorre toda a lista e identifica que o menor valor é 1, localizado na última posição; ele troca esse valor com o primeiro elemento, resultando em [1, 2, 8, 5].
Na segunda rodada, a varredura considera apenas os valores a partir da segunda posição (2, 8, 5) e encontra 2 como o menor valor, que já está no lugar correto, mantendo a lista [1, 2, 8, 5].
Na terceira rodada, a varredura analisa (8, 5) e identifica 5 como o menor valor restante, trocando-o com 8: a lista passa a ser [1, 2, 5, 8]. Como resta apenas um elemento, a lista está ordenada.
Esse exemplo é ilustrativo e serve para mostrar o padrão de varredura, identificação do menor valor e troca ao final de cada rodada, sem representar um caso real medido.
Em ordem crescente, o algoritmo pode ser descrito nos seguintes blocos lógicos, cada um correspondendo a uma etapa do processo:
Esse pseudocódigo evidencia o ponto central do algoritmo: a comparação ocorre continuamente, mas a troca é um evento único por rodada, realizado apenas depois que o menor valor da rodada foi confirmado.
Para contextualizar o desempenho do Selection Sort, é útil compará-lo ao Bubble Sort, outro algoritmo simples de ordenação.
O Bubble Sort tem melhor caso O(n), quando a lista já está ordenada, e pior caso O(n²), quando a lista está em ordem inversa ou totalmente desorganizada.
O Selection Sort apresenta um desempenho um pouco superior ao Bubble Sort porque reduz o número de trocas realizadas — cada rodada faz, no máximo, uma troca, enquanto o Bubble Sort pode realizar várias trocas por rodada.
Essa diferença, porém, não muda a classe de complexidade do algoritmo: o Selection Sort continua pertencendo ao grupo de algoritmos quadráticos, adequados a listas pequenas, mas pouco eficientes para volumes grandes de dados.
O Insertion Sort recebe esse nome porque simula o processo de inserir um novo valor em um conjunto já ordenado.
Ele parte do princípio de que uma lista com um único elemento já está ordenada e, a cada rodada, insere o próximo valor na posição correta dentro da parte já organizada.
Essa lógica torna o Insertion Sort um algoritmo estável, ou seja, ele preserva a ordem relativa de elementos considerados iguais.
Sua complexidade no pior caso e na média também é O(n²), semelhante à do Selection Sort, embora a forma como cada um chega a esse resultado seja diferente.
A tabela a seguir resume as principais diferenças de funcionamento entre os dois algoritmos.
| Critério | Selection Sort | Insertion Sort |
|---|---|---|
| Princípio de ordenação | Seleciona o menor valor restante a cada rodada | Insere cada novo valor na posição correta da parte já ordenada |
| Ponto de partida | Considera toda a lista como não ordenada no início | Considera o primeiro elemento como uma lista já ordenada de tamanho um |
| Número de trocas | Até uma troca por rodada | Pode deslocar vários elementos a cada inserção |
| Complexidade no pior caso | O(n²) | O(n²) |
Porque, a cada rodada, o algoritmo seleciona explicitamente o menor valor restante na lista antes de posicioná-lo. Esse ato de seleção repetida é o que dá nome ao método.
O algoritmo percorre todos os valores ainda não ordenados, compara-os entre si e guarda a posição do menor valor encontrado. Só depois de concluir essa varredura ele troca esse valor para a posição correta.
Na prática, o Selection Sort costuma realizar menos trocas de posição do que o Bubble Sort, o que pode representar uma vantagem de desempenho. Ainda assim, os dois pertencem à mesma classe de complexidade quadrática, então essa vantagem não é garantida em todos os cenários.
O Selection Sort é classificado como um algoritmo de complexidade quadrática, na mesma categoria de algoritmos simples como o Bubble Sort, por exigir comparações repetidas entre todos os elementos restantes em cada rodada.
O Selection Sort busca ativamente o menor valor restante em toda a lista não ordenada antes de posicioná-lo. O Insertion Sort, por outro lado, parte de uma pequena lista já ordenada e insere cada novo valor na posição correta dentro dela, deslocando elementos quando necessário.
O Selection Sort é indicado para listas pequenas ou para fins didáticos, quando a simplicidade de implementação é mais importante do que o desempenho em grandes volumes de dados. Para listas maiores, algoritmos com lógica diferente tendem a ser mais adequados.
Se você quer ingressar ou crescer no mercado da tecnologia, a Allevo Tech oferece formações práticas em áreas de alta demanda, como Engenharia de Software, Ciência de Dados e Inteligência Artificial.
As trilhas são estruturadas para desenvolver competências técnicas e preparar você para os desafios do mercado de trabalho.
Clique no botão abaixo e conheça as formações da Allevo Tech que podem impulsionar a sua trajetória profissional.
Em resumo: Ver a mensagem de que o aplicativo não foi instalado após longos minutos de espera é um dos maiores pesadelos dos usuários de Android. O aviso costuma aparecer logo no final do processo, sem dar muitas explicações e sem apontar para uma solução. Felizmente, resolver esse erro costuma ser bem mais simples do […]
Descubra os melhores aplicativos de produtividade para organizar tarefas, gerenciar o tempo e melhorar o foco
Use o checklist de supermercado com alimentos, bebidas, limpeza e higiene. Marque os itens e ajuste as quantidades à rotina e ao orçamento da sua casa.
