Bubble Sort

Bubble sort repeatedly swaps adjacent inverted elements. After each pass, the largest remaining element reaches its final position.

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;
    }
}

After a pass ending at index end, values[end] is the maximum of the remaining prefix and is in its final position. The early-exit best case is Θ(n); average and worst cases are Θ(n²). It uses Θ(1) auxiliary space and is stable because equal elements are not swapped.