Theory

Bubble sort is a very useful tool for teaching the basics of sorting, time and space complexity, while not being a very efficent algorithm. (even being one of the slowest)

Bubble sort works by going through a list of length n many times, and comparing the current index and the next index. If the right is smaller than the left, they two get switched. By the first pass, the rightmost item is sorted (highest) and can be skipped. By the second pass, the last 2 elements are sorted, and so on.

The O(n) function shows how much time the algorithm takes with an input of n size. In this case, the best case (already sorted) is O(n) time, and the average/worst case is O(n^2) (1 item = 1 unit. 2 items = 4 units, so on...)

Because of this, it is seen as an introduction to sorting algorithms, with its simplicity and easiness to code.

Algorithm Intro

Now, we will code the algorithm using Python 3.
Lets say this is our initial list:

unsorted = [2, 7, 9, 4, 3, 6, 5, 10, 8, 1]

This is how it would be sorted:

  1. [2, 7, 9, 4, 3, 6, 5, 10, 8, 1]
  2. [2, 7, 4, 3, 6, 5, 9, 8, 1, 10]
  3. [2, 4, 3, 6, 5, 7, 8, 1, 9, 10]
  4. [2, 3, 4, 5, 6, 7, 1, 8, 9, 10]
  5. [2, 3, 4, 5, 6, 1, 7, 8, 9, 10]
  6. [2, 3, 4, 5, 1, 6, 7, 8, 9, 10]
  7. [2, 3, 4, 1, 5, 1, 7, 8, 9, 10]
  8. [2, 3, 1, 4, 6, 1, 7, 8, 9, 10]
  9. [2, 1, 3, 5, 6, 1, 7, 8, 9, 10]
  10. [1, 2, 4, 5, 6, 1, 7, 8, 9, 10]
  11. [1, 3, 4, 5, 6, 1, 7, 8, 9, 10]

Building the Algorithm

Lets start with the basic function to swap two items:

def swap(arr, a, b): arr[a], arr[b] = arr[b], arr[a] return arr

And an iterator to iterate through the list:

sorted = unsorted length = len(sorted) for run in range(0, length-1): for index in range(0, length-run-1): # code to swap

We swap when the left is greater than the right, so the full code is as follows:

unsorted = [2, 7, 9, 4, 3, 6, 5, 10, 8, 1] def swap(arr, a, b): arr[a], arr[b] = arr[b], arr[a] return arr sorted = unsorted print(unsorted) length = len(sorted) for run in range(0, length-1): for index in range(0, length-run-1): if sorted[index] > sorted[index+1]: sorted = swap(sorted, index, index+1) print(sorted)
Running

Now, we run the program and get the following output:

[2, 7, 9, 4, 3, 6, 5, 10, 8, 1] [2, 7, 4, 3, 6, 5, 9, 8, 1, 10] [2, 4, 3, 6, 5, 7, 8, 1, 9, 10] [2, 3, 4, 5, 6, 7, 1, 8, 9, 10] [2, 3, 4, 5, 6, 1, 7, 8, 9, 10] [2, 3, 4, 5, 1, 6, 7, 8, 9, 10] [2, 3, 4, 1, 5, 6, 7, 8, 9, 10] [2, 3, 1, 4, 5, 6, 7, 8, 9, 10] [2, 1, 3, 4, 5, 6, 7, 8, 9, 10] [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Just as expected!

Conclusion

The bubble sort is incredibly inneficent, with a lot of faster algorithms like insertion, and the currently fastest quicksort being used for actual implementations. It is a great way to introduce the time and space complexity of algorithms, having a very simple pattern it follows.

Loading...