Ordenação por Seleção

O algoritmo de ordenação por seleção (selection sort) consiste em, dado um vetor de entrada, procurar o menor elemento do vetor e colocá-lo na primeira posição, então repete o processo para segunda, terceira, etc., posições.

Obtendo o Menor Valor

A tarefa mais importante desse algoritmo é encontrar o menor elemento de um vetor. Para isso basta considerar o primeiro item como o menor e então percorrer o vetor buscando alguém menor, se encontrar, a gente descarta o item considerado menor até então e considera o atual como o menor. Acompanhe:

public class AlgorithmsTest {
    public static void main(String[] args) {
        int[] vector = {9,8,7,6,5,4,3,2,1,0};

        int minValue = vector[0];
        for (int i = 1; i < vector.length; i++) {
            if(minValue > vector[i])
                minValue = vector[i];
        }

        System.out.println(minValue);
    }
}

Isso deverá imprimir 0 (zero). Um ponto a considerar é que percorremos o vetor a partir da posição 1 (segunda posição, no caso) porque a primeira a gente já obteve fora do laço. Outro ponto é que iniciamos o vetor diretamente sem usar o new e nem especificar seu tamanho. Outras formas de criar um vetor em java:

int[] vector = new int[10];

Os colchetes também podem aparecer depois do nome da variável:

int vector[] = new int[10];

Ok, já sabemos como obter o menor item de um vetor. Agora tudo que precisamos é extrair esse código pra um método para reutilizar ele depois:

private static int getMinValue(int[] vector) {
        int minValue = vector[0];
        for (int i = 1; i < vector.length; i++) {
            if(minValue > vector[i])
                minValue = vector[i];
        }
        return minValue;
    }

Isso pode ser feito selecionado a porção de código desejada e usando o atalho Ctrl + Alt + M no IntelliJ.

Ordenando o vetor

Agora que já sabemos obter o menor valor de um vetor, basta percorrer o vetor de entrada, obter o menor valor dele e colocar na primeira posição, feito isso, buscamos o segundo menor valor, o terceiro menor valor, etc.. Seria mais fácil entender caso estivéssemos construindo um novo vetor, pois bastaria fazer algo como:

int[] vector2 = new int[10];
for (int i = 0; i < vector2.length; i++) {
    vector2[i] = getMinValue(vector);
}

Isso não funciona porque o método que busca o menor valor vai retornar exatamente isso: o menor valor. Para funcionar, teríamos que obter o menor valor sem considerar o antigo menor valor. Existem muitas maneiras de fazer isso, mas é melhor unir o processo de 'criação' do novo vetor com o processo de obter o menor valor de um vetor fazendo ambas operações no mesmo vetor. Isso é feito da seguinte forma:

1. obtém o menor valor do vetor e coloca ele na posição 0.
2. obtém o menor valor do vetor desconsiderando a posição 0 e coloca ele na posição 1
3. obtém o menor valor do vetor desconsiderando a posição 0 e 1 e coloca ele na posição 2
4. etc...

No código isso equivale a percorrer o vetor da posição 0 até o final, e para cada posição percorre o vetor novamente a partir dessa posição até o final procurando o menor item e quando encontrar, trocar com o item atual. Tente visualizar (abstrair) isso pensando que sua busca pelo menor tá sempre sendo feita na parte direita do vetor e a parte esquerda está recebendo os valores menores um após o outro. Acompanhe o seguinte código:

private static void selectionSort(int[] vector) {
        for (int i = 0; i < vector.length - 1; i++) {
            for (int j = i; j < vector.length; j++) {
                if (vector[j] < vector[i]) {
                    int temp = vector[j];
                    vector[j] = vector[i];
                    vector[i] = temp;
                }
            }
        }
    }

Imagine que o vetor está ordenado de forma inversa (o pior caso):

[4,3,2,1,0]

O laço mais externo vai percorrer esse vetor. No laço mais interno vamos percorrer o vetor começando da posição 'i'. Note que dentro do laço mais interno temos sempre que para 'i' estamos lidando com os valores a esquerda do vetor e para 'j' com os valores a direita do vetor. Por exemplo, se 'i' for igual 2, então 'j' vai trabalhar com 2,3 e 4, e 'i' já passou por 0, 1 e 2.

Considerações Finais

Mais importante que entender a ordenação em si, nesse momento, é entender a lógica desses fors aninhados, pois esse tipo de operação é muito comum e é importante conseguir abstrair isso.

Segue o código completo, incluindo o método getMinValue:

package com.nttdata.willams.algoritmos;

import java.util.Arrays;

public class AlgorithmsTest {
    public static void main(String[] args) {
        int[] vector = {9,8,7,6,5,4,3,2,1,0};

        int minValue = getMinValue(vector);
        System.out.println(minValue);

        selectionSort(vector);

        System.out.println(Arrays.toString(vector));
    }

    private static void selectionSort(int[] vector) {
        for (int i = 0; i < vector.length - 1; i++) {
            for (int j = i; j < vector.length; j++) {
                if (vector[j] < vector[i]) {
                    int temp = vector[i];
                    vector[i] = vector[j];
                    vector[j] = temp;
                }
            }
        }
    }
    private static int getMinValue(int[] vector) {
        int minValue = vector[0];
        for (int i = 1; i < vector.length; i++) {
            if(minValue > vector[i])
                minValue = vector[i];
        }
        return minValue;
    }
}

Acredito que você tenha entendido. No próximo artigo vamos estudar o Insertion Sort. Até lá!