Ordenação por Comparação: Selection Sort

Direto ao ponto

Se você pedir para alguém que não é familiarizado com algoritmos para que ordene uma sequência de números, há uma probabilidade alta dessa pessoa aplicar o Selection Sort. Isso porque esse algoritmo tem uma rotina básica muito simples e direta: selecionar (daí o nome Selection Sort) o menor elemento da sequência e colocar esse elemento na primeira posição do array. A ideia é executar várias vezes esses dois passos para ordenar um array. Para ser exato, se executarmos $N$ vezes esses dois passos em um array, controlando os índices em que os passos são executados, o resultado é a ordenação completa do mesmo.

Selection Sort

Selecionando o menor

Este algoritmo é elementar. Basta percorrer o array comparando os elementos para determinar qual é o menor. No início, assumimos que o menor elemento está no índice 0 (indice_menor = 0) e iteramos a partir do segundo índice comparando os elementos.

...
	// encontra o índice do menor elemento
	int indice_menor = 0;
	for (int i = 1; i < v.length; i++) {
		if (v[i] < v[indice_menor])
			indice_menor = i;
	}

	// coloca o menor na primeira posição
	int aux = v[0];
	v[0] = v[indice_menor];
	v[indice_menor] = aux;
}
...

Ao fim da execução deste algoritmo temos uma certeza: o menor elemento está no índice 0 do array.

Como usar esta rotina para ordenar um array?

Ora, basta repetir esse mesmo processo para o restante do array. Vamos ver a execução para o $values = [70, 90, 1, 3, 0, 100, 2]$

Na primeira execução, 0 é o menor valor. Encontramos esse valor e trocamos com a primeira posição (70).

[70, 90, 1, 3, 0, 100, 2]

[0, 90, 1, 3, 70, 100, 2]

Agora, aplicamos a mesma ideia para o restante do array, ou seja, no intervalo de índices $[1, values.length - 1]$.

[0, 90, 1, 3, 70, 100, 2]

[0, 1, 90, 3, 70, 100, 2]

Depois, aplicamos a mesma ideia para o restante do array, ou seja, no intervalo de índices $[2, values.length - 1]$.

[0, 1, 90, 3, 70, 100, 2]

[0, 1, 2, 3, 70, 100, 90]

Continuamos aplicando a mesma ideia para o restante do array, ou seja, no intervalo de índices $[3, values.length - 1]$. Como 3 já está no seu lugar, ele será trocado por ele mesmo. O mesmo acontece com o intervalo de índices $[4, values.length - 1]$, onde 70 já está em sua posição.

Aplicando, então, para o intervalo de índices $[5, values.length - 1]$, temos:

[0, 1, 2, 3, 70, 100, 90]

[0, 1, 2, 3, 70, 90, 100]

Por fim, aplicado para o intervalo $[6, values.length - 1]$, temos que 100 já está em sua posição.

Feito! O array está ordenado. Note que apenas executamos a rotina de encontrar o menor e colocar na primeira posição várias vezes. Para ser exato, executamos $N$ vezes, variando a faixa de valores que o algoritmo deve avaliar.

...
public static void selectionSort(int[] v) {	
	for (int i = 0; i < v.length; i++) {
		
		int i_menor = i;
		for (int j = i + 1; j < v.length; j++)
			if (v[j] < v[i_menor])
				i_menor = j;
		
		int aux = v[i];
		v[i] = v[i_menor];
		v[i_menor] = aux;
	
	}		
}
...

Abaixo podemos ver uma animação produzida pelo TutorialHorizon.

Eu também gravei um vídeo explicando o Selection Sort.

Propriedades e Análise de eficiência

O Selection Sort é in-place e $O(n^2)$, mas não é estável.

Lembrando que estabilidade é uma propriedade relacionada à ordem relativa de valores iguais no array original. Por exemplo, se houver dois valores 97 no array antes da ordenação, após a execução do algoritmo, esses dois valores devem seguir a ordem relativa inicial. Ou seja, ao término da execução do algoritmo, a primeira ocorrência do 97 deve vir antes da segunda ocorrência do 97.

O Selection Sort não é estável porque dependendo das trocas, ele não mantém a ordem relativa dos valores iguais. Vamos analisar um exemplo em que isso acontece. Para diferenciar valores iguais, vou colocar os subscritos $a$ e $b$, ok?

$values = [1, 7_a, 7_b, 2] $

Na primeira iteração, o menor valor é 1 e, por isso, fica na posição em que está. Depois, na segunda iteração o menor valor é 2 e deve trocar de lugar com $7_a$. O resultado parcial é:

$values = [1, 2, 7_b, 7_a] $

Na terceira iteração $7_b$ é o menor e fica no lugar em que está. Na última iteração $7_a$ já o menor do array restante e fica no lugar em que está.

Como resultado, temos que $7_a$ vinha antes de $7_b$ no array original, mas essa ordem relativa foi trocada depois da ordenação. Portanto, o algoritmo não é estável.

O Selection Sort é in-place porque a ordenação é feita rearranjando os elementos no próprio array, ao invés de usar arrays ou outras estruturas auxiliares.

O Selection Sort é $O(n^2)$. A busca pelo menor elemento custa $n - 1$ passos na primeira iteração, $n - 2$ passos na segunda, $n - 3$ passos na terceira e assim por diante. Assim como no caso do Insertion Sort, o custo é dado pela soma dos termos da Progressão Aritmética $1 + 2 + 3 + … + (n - 1)$, com $a_1 = 1$ e $a_n = (n - 1)$ e razão $r=1$. A soma dos termos de uma PA é dada por: $(a_1+a_n)*n/2$. Então, temos que o tempo de execução do algoritmo é dado por $(1 + (n - 1)) * (n - 1)/2 = n * (n - 1)/2 = (n^2)/2$. Aplicando as diretrizes de simplificação, o Selection Sort é $\Theta(n^2)$.

É importante traçar o paralelo entre o Selection Sort e o Insertion Sort. O Selection efetua menos trocas do que o Insertion, pois há uma troca apenas por iteração, ou seja, no total o Selection Sort efetua $n$ trocas. Já o insertion sort efetua ao menos uma troca por iteração, pois deve efetuar trocas para afastar cada elemento avaliado.

Por outro lado, o Insertion Sort efetua menos comparações do que o Selection Sort, pois nem sempre o elemento a ser inserido de forma ordenada deve ir até o final. Na verdade, isso só acontece no pior dos casos, em que o array está ordenado em ordem reversa. Já o Selection Sort precisa comparar todos os elementos restante cada vez para determinar quem é o menor deles.

Na teoria, ambos estão na mesma classe de complexidade, qual seja $O(n^2)$. Na prática, o Insertion Sort apresenta melhor desempenho do que o Selection Sort.

Por fim, O Selection Sort não é considerado um algoritmo eficiente para grandes entradas. Há alternativas $O(n*\log n)$, como Quick Sort e Merge Sort, além de alternativas lineares como o Counting Sort.

Resumo

O Selection Sort segue uma rotina bem simples e direta: encontrar o menor elemento e colocá-lo na primeira posição. A ordenação nada mais é do que aplicar essa rotina repetidas vezes para o restante do array.
O Selection sort é in-place e $O(n^2)$.
A implementação clássica do Selection Sort não é estável.
Embora sejam da mesma classe de complexidade, o Selection Sort, na prática, é mais lento do que o Insertion Sort.
O Selection Sort não é considerado um algoritmo eficiente para grandes entradas. Há alternativas $O(n*\log n)$, como Quick Sort e Merge Sort, além de alternativas lineares como o Counting Sort.

Notas

Vale a pena utilizar o VisuAlgo para visualizar a execução do Selection Sort e de outros algoritmos de ordenação.