Bubble Sort

Large elements bubble to the right

Bubble sort repeatedly scans the array from left to right and compares neighboring elements. If the left one is greater than the right one, they are swapped. After one full pass, the largest element in the unfinished part ends up in its final position on the right.

static void bubbleSort(int[] a) {
    for (int end = a.length - 1; end > 0; end--) {
        boolean swapped = false;

        for (int i = 0; i < end; i++) {
            if (a[i] > a[i + 1]) {
                int tmp = a[i];
                a[i] = a[i + 1];
                a[i + 1] = tmp;
                swapped = true;
            }
        }

        if (!swapped) {
            return;
        }
    }
}

The variable end marks the right boundary of the still unsorted part. After each pass, it can be moved left: the element at end is already the largest among the remaining values and no longer needs to be compared.

Why the swapped flag matters

If a complete pass makes no swaps, the array is already sorted and additional passes would change nothing. This check allows nearly sorted data to be processed much faster in some cases.

Complexity

On average and in the worst case, bubble sort performs O(n²) comparisons. With the swapped optimization, an already sorted array takes O(n) time. Extra space is O(1) because all swaps happen inside the original array.