É impressionante como algumas coisas deixam mais marcas do que outras. Dentre todos algoritmos de ordenação que já estudei, o Selection Sort é meu favorito, apesar de ser um dos menos eficientes. Nem por isso ele perdeu o seu brilho. Sempre que eu precisava implementar alguma ordenação no meio do código, era ele que eu utilizava. Talvez por ser fácil de lembrar, ou talvez por ter decorado o código mesmo. O fato é que ele sempre me acompanhou.
O princípio do Selection Sort é muito simples: passe pela lista inteira procurando o menor elemento. Após percorrer a lista inteira e encontrar o menor elemento, mova ele para a primeira posição. Repita então o processo, mas agora desconsiderando o elemento que você moveu. Ao encontrar esse novo valor, mova ele para a segunda posição. Repita esse processo até que toda a lista esteja ordenada. Vamos dar uma olhada em uma ilustração para ficar mais claro.
A primeira coisa que devemos fazer é buscar pelo menor elemento da lista. Nesse caso é o 3.
Então nós movemos o 3 para o começo a lista e passamos a buscar o menor elemento dentre o conjunto que não está ordenado (todos os elementos que estão após o 3).
Por coincidência, o menor elemento desse subconjunto é o 8, que já está na segunda posição. Nesse caso não precisamos realizar trocas.
Vamos então procurar o menor elemento do subconjunto formado a partir do número 8, que nesse caso é o 11.
Após repetir algumas vezes esse processo, obtemos o conjunto inteiro ordenado.
Vamos dar uma olhada em uma implementação simples no Java:
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] v = {20, 8, 87, 70, 34, 11, 3, 59};
System.out.println(Arrays.toString(v));
selectionSort(v);
System.out.println(Arrays.toString(v));
}
public static void selectionSort(int[] v) {
for (int i = 0; i < v.length; i++) {
int iMenor = i;
for (int j = i + 1; j < v.length; j++) {
if (v[j] < v[iMenor]) {
iMenor = j;
}
}
if (i != iMenor) {
int temp = v[i];
v[i] = v[iMenor];
v[iMenor] = temp;
}
}
}
}
Um ponto importante de dizer é que a complexidade desse algoritmo é O(n²), o que o torna menos eficiente que outros algoritmos tais como Quick Sort ou Heap Sort.