Bubble Sort

O Bubble sort troca repetidamente elementos adjacentes que estão invertidos. Depois de cada passagem, o maior elemento restante alcança sua posição final.

static void bubbleSort(int[] values) {
    for (int end = values.length - 1; end > 0; end--) {
        boolean swapped = false;
        for (int i = 0; i < end; i++) {
            if (values[i] > values[i + 1]) {
                int temporary = values[i];
                values[i] = values[i + 1];
                values[i + 1] = temporary;
                swapped = true;
            }
        }
        if (!swapped) return;
    }
}

Após uma passagem que termina no índice end, values[end] é o máximo do prefixo restante e está em sua posição final. Com a saída antecipada, o melhor caso é Θ(n); os casos médio e pior são Θ(n²). O algoritmo usa espaço auxiliar Θ(1) e é estável porque elementos iguais não são trocados.