Title: Implement bubble sort in Python

[The bubble sort algorithm works well with lists that are mostly already sorted]

This example shows how to implement the bubble sort algorithm in Python. The algorithm itself is pretty interesting (at least if you haven't implemented it dozens of times in different languages like I have 😉), but this post is largely as an amuse-bouche before the next post, which shows how to use Pygame to visualize the algorithm.

Algorithm

The basic algorithm is to scan through the list of items. If you find two adjacent items that are out of order, swap them. Repeat until a pass through the list finds no more out-of-order items.

Here's the algorithm in a slightly more precise pseudocode.

Set made_change = True so the following while statement starts its loop.
While made_change is True:
1. Set made_change = False.
2. Loop through the items. If you find two adjacent items that are out of order:
  1. Swap the items.
  2. Set made_change = True to remember that we made a change to the list.
3. Repeat the while loop until made_change remains False after the inner loop in step B.

If you study the picture at the top of this post, you'll see how the algorithm sorts the list. For example, during its first pass through the list, the program swaps the values 3 and 1. It then swaps the values 3 and 2, and 3 and 0. A bit later during this first pass, it swaps 9 and 8, and then 9 and 7.

The later passes through the list continue to swap adjacent items until the list is sorted.

The following section shows a Python implementation that follows the pseudocode closely.

Code

Here's this example's implementation of the algorithm.

def bubble_sort(items): '''Use bubble sort to sort the items.''' num_items = len(items) made_change = True round = 1 while made_change: print(f'Round {round}') made_change = False for i in range(0, num_items - 1): # If items[i] > items[i + 1], swap them. if items[i] > items[i + 1]: show_swap(items, i, i + 1) items[i], items[i + 1] = items[i + 1], items[i] made_change = True round += 1

This code follows the pseudocode closely but with two additions.

First, it keeps track of the algorithm's rounds, during which time it makes a pass through the list. It prints the round number before each pass begins.

Second, when it swaps two adjacent items, it also calls the following show_swap function to print out the swap so you can see what's happening (as shown in the picture at the top of the post).

def show_swap(items, i, j): '''Display the items with the swap marked.''' print(' '.join(str(i) for i in items)) spaces = ' ' * (i * 2) dashes = '\u2501' * (2 * (j - i) - 1) print(f'{spaces}\u2515{dashes}\u2519')

To show the swap of items i and j, this function first prints the list's items joined by space characters.

Next, the code prints Unicode characters like ┕───┙ to show which items were swapped. To do that, it creates two strings: one that contains the necessary number of spaces needed to put the ┕ character below item i, and one that contains the required number of ─ characters to move to the second item at position j. It prints those strings followed by ┙.

Conclusion

Bubble sort has O(N²) performance. In other words, the time it takes bubble sort to sort a list of randomly arranged values is proportional to the square of the number of items in the list. There are many other algorithms with faster performance. For example, quicksort has O(N log N) performance, which is much faster, particularly for large N.

So why, you ask, do we bother with bubble sort? First, because it's an interesting algorithm that's worth studying just to practice building algorithms.

Bubble sort is also faster for lists that are mostly sorted. If you start with a big list and only one or two items are out of place, bubble sort may be faster than O(N log N) algorithms.

Bubble sort is also usually faster for very small lists. If you're only sorting 3 or 4 items, bubble sort is often faster due to its relative simplicity. Other algorithms may be faster for large lists, but they have extra overhead that dominates the run time for really small lists.

So bubble sort is still worth using, at least sometimes. There are several tricks you can use to make it faster, but we won't go there, at least for now. In my next post (or maybe two posts), I'll show how you can use Pygame to visualize bubble sort. Meanwhile, download this example to experiment with it and to see additional details.