Bubble Sort in Java - Quiz

On every pass the smallest (or largest, depending on direction) element gradually rises to the edge of the array, like an air bubble floating up through water. That image is where the name bubble sort comes from.

In the average and worst cases it is O(n²), where n is the number of elements. The best case is O(n), but only in the optimized version with a flag when the array is already sorted. Space complexity is O(1) because it sorts in place.

Add a boolean flag named swapped: if a full pass makes no swaps, the array is already sorted and you can stop the loop with break. This lowers the best-case complexity to O(n) and helps when the data is nearly ordered.

Both run in O(n²), but bubble sort compares and swaps adjacent elements, while selection sort finds the minimum on each pass and makes just one swap. As a result bubble sort does more swaps, yet it is stable, whereas classic selection sort is not.

Yes, bubble sort is a stable sort: equal elements keep their original relative order, because a swap happens only when one element is strictly greater than its neighbour (the condition is array[j - 1] > array[j], not >=). This detail comes up often in interviews.