Bubble Sort

Why it is here at all

Honestly, almost never for actually sorting anything. It is on this site because two genuinely useful ideas live inside it.

The first is the constraint you may only swap neighbours, which turns up in real questions. The second is counting: the number of neighbour swaps needed to sort a list measures how far from sorted it was, and that number is useful on its own.

The idea, plainly

Walk the list comparing each pair of neighbours and swap them when they are the wrong way round. Each full pass drifts the largest remaining item to the end, the way a bubble rises. Repeat until a pass makes no swaps at all.

That last detail, stopping when a pass changes nothing, is what makes it quick on nearly sorted data and is the only reason it is ever acceptable.

Where to start

Implement Bubble Sort and Count Bubble Sort Swaps together.

Bubble Sort Pass Count forces you to add the early exit, because without it the answer is always the same number and the question has no point.

Sort an Array of 0s, 1s, and 2s Using Adjacent Swaps is the first one that feels like a real problem rather than an exercise. Sort a Nearly Sorted Array shows the method at its best, because nothing is far from home and few passes are needed.

Minimum Adjacent Swaps to Sort an Array is the payoff, and it hides a trap. The answer is the number of out-of-order pairs, but you have to count them, not perform them. Actually bubbling through a large list to count is far too slow. Counting them during a merge sort is fast. Bubble sort tells you what to count and a different method does the counting.

Common mistakes

Leaving out the early exit and concluding the method is hopeless even on sorted data.

Performing the swaps when the question only asks how many there would be.

Re-scanning the settled tail on every pass. After each pass the end is final and can be skipped.