Originally published on CodingCush .
Bubble sort is a simple sorting algorithm that compares neighbouring items again and again and swaps them whenever they are in the wrong order. After each full pass, the biggest unsorted value has bubbled up to its correct place at the end. In this guide you will dry run bubble sort on a small list, write the basic Python version, improve it with a swapped flag, count its comparisons and swaps, and see how it compares with Python's built in sorted(). Every output comes from running this article's code on Python 3.12.3.
How Bubble Sort Works, in Plain Words
Imagine students lined up by height, but shuffled. You walk along the line looking at each pair of neighbours. Whenever the taller student stands in front of the shorter one, they swap. By the end of the walk, the tallest student is at the back, having won every swap.
That walk is called a pass. On the next pass, the second tallest ends up just before the tallest. Pass by pass, the sorted part grows at the end.…