Selection Sort

O Selection sort encontra o menor elemento do sufixo não ordenado e o troca com a próxima posição da saída.

static void selectionSort(int[] values) {
    for (int destination = 0; destination < values.length - 1; destination++) {
        int minimum = destination;
        for (int scan = destination + 1; scan < values.length; scan++) {
            if (values[scan] < values[minimum]) minimum = scan;
        }
        int temporary = values[destination];
        values[destination] = values[minimum];
        values[minimum] = temporary;
    }
}

Antes de cada iteração externa, o prefixo anterior a destination contém os menores valores originais em suas posições finais ordenadas. Selecionar o mínimo do sufixo restante estende esse invariante em uma posição.

O Selection sort realiza n(n - 1)/2 comparações nos casos melhor, médio e pior; portanto, o tempo é Θ(n²). Ele usa espaço auxiliar Θ(1) e no máximo n - 1 trocas. Esta implementação comum não é estável, pois uma troca a longa distância pode mover um item para depois de outro com a mesma chave. Pode ser útil quando escritas custam muito mais do que comparações, mas seu uso é principalmente pedagógico.