O Selection Sort é um algoritmo de ordenação simples e intuitivo que ordena um array selecionando repetidamente o elemento mínimo da parte não ordenada e colocando-o no início. Embora não seja tão eficiente quanto algoritmos mais avançados, como quicksort ou mergesort, o selection sort é fácil de entender e é adequado para conjuntos de dados pequenos.
O algoritmo divide o array de entrada em duas partes: uma seção ordenada e uma seção não ordenada. Ele itera selecionando repetidamente o elemento mínimo da seção não ordenada e trocando-o com o primeiro elemento da seção não ordenada, estendendo assim a seção ordenada.
- Comece considerando todo o array como não ordenado.
- Itere pela seção não ordenada para encontrar o elemento mínimo.
- Troque o elemento mínimo com o primeiro elemento da seção não ordenada.
- Mova a fronteira entre as seções ordenada e não ordenada para a direita.
- Repita os passos 2-4 até que todo o array esteja ordenado.
| Caso | Complexidade |
|---|---|
| Pior | O(n^2) |
| Médio | O(n^2) |
| Melhor | O(n^2) |
| Caso | Complexidade |
|---|---|
| Pior | O(1) |
| Médio | O(1) |
| Melhor | O(1) |
O algoritmo não é estável, pois pode alterar a ordem relativa de elementos iguais.