Algoritmo: Selection Sort

Continuando a série sobre algoritmos de ordenação, hoje falarei sobre o Selection Sort.

O Selection Sort funciona de forma semelhante ao Bubble Sort. A principal diferença é durante a análise de qual número vai naquela casa, não é feito a troca imediatamente, mas sim guardado a referência para aquela posição (no pseudo-código abaixo, essa referência é guardada na variável “menor”). 


Depois de verificado todos os valores para a posição i, ele verifica se é necessária a troca (linha 09 do psudo-código). Se for necessária, ele realiza a troca da mesma maneira que o Bubble Sort, caso contrário segue com o algoritmo.
Esse método tem um desempenho um pouco superior ao Bubble Sort por evitar o processamento de troca a cada troca potencialmente correta, fazendo a mesma ocorrer somente o necessário, entretanto, essa melhora não é tão significativa para que altere a sua complexidade algorítmica.

 O Pseudocódigo do Selection Sort para ordem crescente é o seguinte :

01. var i,j,aux,menor : INTEIRO
02. PARA i=0 ATE (vet.tamanho-1) PASSO 1
03.  menor = i
04.  PARA j=i+1 ATE vet.tamanho PASSO 1
05.   SE (vet[menor] > vet[j]) ENTAO
06.    menor = j
07.   FIMSE
08.  FIMPARA
09.  SE (menor != i) ENTAO
10.   aux = vet[menor]
11.   vet[menor] = vet[i]
12.   vet[i] = aux
13.  FIMSE
14. FIMPARA


Vamos analisar esse algoritmo com um vetor com os seguintes valores: {55, 76, 26, 64, 26, 80, 71, 46} e organizá-los em ordem crescente:
Assim como o Bubble Sort, é utilizada duas variáveis para percorrer o vetor desde o início:
 
Entretanto, antes de iniciar a análise, uma variável marca a casa inicial como o valor válido para a posição, nesse caso, é a variável “menor:
Então, compara-se os valores da posição j com a posição do menor.
Se for falso, vamos verificar a próxima posição:
Agora, vamos é verificado a posição do menor valor com a posição j:
Agora que foi verdadeiro, ao invés de fazer a troca, como no Bubble Sort, vamos simplesmente indicar que o menor valor agora é a que está na posição j:
E o ciclo vai repetir até que o j atinja a última posição:

Depois que o j percorreu todas as posições, verificamos se é necessário a troca de posição, comparando o índice indicado pela variável i com o índice que indica o menor valor:
 
Se os índices são diferentes, significa que é necessário fazer a troca entre os dois valores, esse segue a mesma ideia do que o Bubble Sort:
Depois de que a troca foi feita, a variável i avança para a póxima posição e o menor valor é resetado para a posição i atual:
E a partir daqui, inicia-se novamente o ciclo de verificação:

Teste de mesa para o restante do processamento:

• Negrito indica que as variáveis i ou j estão apontando;
• Sublinhado onde o “menor” está apontando;
• * significa que vai ocorrer a troca;

i	j	menor	vet
1	2	2	{26,76,55,64,26,80,71,46}
1	3	2	{26,76,55,64,26,80,71,46}
1	4	4	{26,76,55,64,26,80,71,46}
1	5	4	{26,76,55,64,26,80,71,46}
1	6	4	{26,76,55,64,26,80,71,46}
1	7	4	{26,76,55,64,26,80,71,46}*
2	3	2	{26,26,55,64,76,80,71,46}
2	4	2	{26,26,55,64,76,80,71,46}
2	5	2	{26,26,55,64,76,80,71,46}
2	6	2	{26,26,55,64,76,80,71,46}
2	7	7	{26,26,55,64,76,80,71,46}*
3	4	3	{26,26,46,64,76,80,71,55}
3	5	3	{26,26,46,64,76,80,71,55}
3	6	3	{26,26,46,64,76,80,71,55}
3	7	7	{26,26,46,64,76,80,71,55}*
4	5	4	{26,26,46,55,76,80,71,64}
4	6	6	{26,26,46,55,76,80,71,64}
4	7	7	{26,26,46,55,76,80,71,64}*
5	6	6	{26,26,46,55,64,80,71,76}
5	7	6	{26,26,46,55,64,80,71,76}*
6	7	7	{26,26,46,55,64,71,80,76}*
7	7	7	{26,26,46,55,64,71,76,80}