Algoritmo de ordenação que encontra o menor elemento e o coloca na posição correta, repetindo para o restante do array.
O Selection Sort divide o array em duas partes: ordenada (à esquerda) e não ordenada (à direita). A cada iteração, encontra o menor elemento na parte não ordenada e o move para o final da parte ordenada. A ideia é simples: selecione o menor, coloque no início. Selecione o segundo menor, coloque na segunda posição. E assim por diante. Comparado ao Bubble Sort, o Selection Sort faz menos trocas (no máximo n-1), mas o mesmo número de comparações. Na prática, ambos são O(n²) e não são usados em produção para grandes datasets.
“O Selection Sort minimiza o número de trocas, fazendo no máximo n-1 trocas. Útil quando a operação de troca é cara.”
Dois loops aninhados. O externo roda n vezes, o interno roda em média n/2.
Comparações: (n-1) + (n-2) + ... + 1 = n(n-1)/2 = O(n²)
Ordena in-place. Só usa variáveis auxiliares para índice e troca.
Mesmo com array já ordenado, ainda precisa verificar todos os elementos para encontrar o mínimo.
Sempre faz o mesmo número de comparações, independente da entrada.
| Algoritmo | Tempo | Espaco | Estavel | Melhor Para |
|---|---|---|---|---|
| Selection Sort(atual) | O(n²) | O(1) | Nao | Quando trocas são caras, arrays pequenos |
| Bubble Sort | O(n²) | O(1) | Sim | Arrays pequenos, fins didáticos |
| Insertion Sort | O(n²) | O(1) | Sim | Arrays pequenos, dados chegando em streaming |
| Merge Sort | O(n log n) | O(n) | Sim | Grandes datasets, quando estabilidade importa |
Pratique respondendo a perguntas comuns de entrevistas tecnicas. Clique em uma pergunta para iniciar uma sessao de pratica com IA.
1def selection_sort(array):Definição2 n = len(array)3 4 for i in range(n - 1):Loop Externo5 min_index = iÍndice do Mínimo6 7 for j in range(i + 1, n):Loop Interno8 if array[j] < array[min_index]:Encontrar Mínimo9 min_index = j10 11 if min_index != i:Troca12 array[i], array[min_index] = array[min_index], array[i]13 14 return array15