Bubble Sort

Task: Sort this array in ascending order

for (int i = 0; i < n - 1; i++) {    boolean swapped = false;    for (int j = 0; j < n - 1 - i; j++) {        if (a[j] > a[j + 1]) {            swap(a, j, j + 1);            swapped = true;        }    }    if (!swapped) break;   // already in order}

What you are watching

Bubble sort compares each neighbouring pair in turn and swaps them when they are out of order, so the largest remaining value is carried to the end of the array on every pass. Sorting 5, 1, 4, 2, 8 takes three passes: the first settles 8 at the end, the second settles 5, and the third compares every remaining pair without swapping anything - which sets the swapped flag to false and ends the sort early. That early exit is why an already-sorted array costs one pass rather than n.