Prev - #41 ROT 13 Encryption | Table of Contents

Exercise #42: Bubble Sort

bubbleSort([2, 0, 4, 1, 3]) → [0, 1, 2, 3, 4]

Bubble sort is often the first sorting algorithm taught to computer science students. While it is too inefficient for use in real-world software, the algorithm is easy to understand. In this last exercise of the book, we’ll implement this basic sorting algorithm.

Exercise Description

Write a bubbleSort() function with a list parameter named numbers. The function rearranges the values in this list in-place. The function also returns the now-sorted list. There are many sorting algorithms, but this exercise asks you to implement the bubble sort algorithm.

The objective of this exercise is to write a sorting algorithm, so avoid using Python’s sort() method or sorted() function as that would defeat the purpose of the exercise.

These Python assert statements stop the program if their condition is False. Copy them to the bottom of your solution program. Your solution is correct if the following assert statements’ conditions are all True:

assert bubbleSort([2, 0, 4, 1, 3]) == [0, 1, 2, 3, 4]

assert bubbleSort([2, 2, 2, 2]) == [2, 2, 2, 2]

Try to write a solution based on the information in this description. If you still have trouble solving this exercise, read the Solution Design and Special Cases and Gotchas sections for additional hints.

Prerequisite concepts: lists, for loops, range() with two arguments, nested loops, swapping values

Solution Design

The bubble sort algorithm compares every pair of indexes and swaps their values so that the larger value comes later in the list. As the algorithm runs, the larger numbers “bubble up” towards the end, hence the algorithm’s name. We’ll use variables named i and j to track the two indexes whose values should be compared with each other. The pattern behind the movements of i and j are easier to see when visually laid out, as in Figure 42-1 which uses a 5-item numbers list as an example:

Figure 42-1: The pattern of i and j’s movement: j starts after i and moves to the right, and when it reaches the end, i moves right once and j starts after i again.

Notice the similarity between the movement of i and j to the nested for loops in Project #26 “Handshakes.” As the algorithm runs, j starts after i and moves to the right, and when it reaches the end, i moves right once and j starts after i again.

If you look at the overall range of i and j, you’ll see that i starts at index 0 and ends at the second to last index. Meanwhile, j starts at the index after i and ends at the last index. This means our nested for loops over the numbers list parameter would look like this:

for i in range(len(numbers) - 1):

for j in range(i, len(numbers)):

Inside the inner loop, the numbers at indexes i and j are compared, and if the number at index i is larger than the number at index j, they are swapped. Figure 42-2 shows the state of a list [8, 2, 9, 6, 3] as the bubble sort algorithm swaps the two numbers after being compared at each step.

Figure 42-2: The steps of the bubble sort algorithm as it sorts [8, 2, 9, 6, 3].

At the end of these two nested for loops, the numbers in the list will have been swapped into sorted order.

Special Cases and Gotchas

Sorting algorithms are an excellent introduction to the computer science topic of data structures and algorithms. And bubble sort is a good introduction to sorting algorithms. But the chief weakness of bubble sort is that it’s incredibly inefficient. While it can quickly sort lists of a few dozen or few hundred values, it becomes infeasible for sorting lists of thousands or millions of values. For this reason, real-world applications never use bubble sort.

Now try to write a solution based on the information in the previous sections. If you still have trouble solving this exercise, read the Solution Template section for additional hints.

Solution Template

Try to first write a solution from scratch. But if you have difficulty, you can use the following partial program as a starting place. Copy the following code from https://invpy.com/bubblesort-template.py and paste it into your code editor. Replace the underscores with code to make a working program:

def bubbleSort(numbers):

# The outer loop loops i over all but the last number:

for i in range(len(____) - ____):

# The inner loop loops j starting at i to the last number:

for j in range(____, len(____)):

# If the number at i is greater than the number at j, swap them:

if numbers[i] ____ numbers[j]:

numbers[i], numbers[j] = numbers[____], numbers[____]

# Return the now-sorted list:

return numbers

The complete solution for this exercise is given in Appendix A and https://invpy.com/bubblesort.py. You can view each step of this program as it runs under a debugger at https://invpy.com/bubblesort-debug/.