Bubble Sort

Bubble sort is a simple, inefficient sorting algorithm used to sort lists. It is generally one of the first algorithms taught in computer science courses because it is a good algorithm to learn to build intuition about sorting. While sorting is a simple concept, it is a basic principle used in complex computer programs such as file search, data compression, and path finding. Running time is an important thing to consider when selecting a sorting algorithm since efficiency is often thought of in terms of speed. Bubble sort has an average and worst-case running time of $O\big(n^2\big)$, so in most cases, a faster algorithm is more desirable. image1

An algorithm that maps the following input/output pair is called a sorting algorithm:

Input: An array, $A$, that contains $n$ orderable elements: $A[0,1,...,n-1]$.

Output: A sorted permutation of $A$, called $B$, such that $B[0] \leq B[1] \leq \cdots \leq B[n-1].$

Here is what it means for an array to be sorted.

An array $<a_n>$ is sorted if and only if for all $i<j$, $a_i \leq a_j.$

In other words, a sorted array is an array that is in a particular order. For example, $[a,b,c,d]$ is sorted alphabetically, $[1,2,3,4,5]$ is a list of integers sorted in increasing order, and $[5,4,3,2,1]$ is a list of integers sorted in decreasing order.

By convention, empty arrays and singleton arrays (arrays consisting of only one element) are always sorted. This is a key point for the base case of many sorting algorithms.

The Bubble sort algorithm compares each pair of elements in an array and swaps them if they are out of order until the entire array is sorted. For each element in the list, the algorithm compares every pair of elements.

The bubble sort algorithm is as follows:

1. Compare $A[0]$ and $A[1]$. If $A[0]$ is bigger than $A[1]$, swap the elements.
2. Move to the next element, $A[1]$ (which might now contain the result of a swap from the previous step), and compare it with $A[2]$. If $A[1]$ is bigger than $A[2]$, swap the elements. Do this for every pair of elements until the end of the list.
3. Do steps 1 and 2 $n$ times.

The animation below illustrates bubble sort:

$\hspace{4cm}$ image1

Sort the array $A=[7,3,1,4,2]$ using the bubble sort algorithm. Show all of the steps that the algorithm takes.

---

The steps are summarized in the following table:

image2

Here is pseudo-code describing the algorithm:

1
2
3
4
5
6

Bubble-sort(a)
1  for i = a.length() to 1
2       for j = 1 to i-1
3                 if a[j]>a[j+1]
4                          swap(a[j],a[j+1]);
5                 end if

This is how the code works:

First, it goes from $j=1$ to $j=N-1$ comparing each element of the list with the next $\big($i.e. the $(j+1)^\text{th}$ element$\big).$ If the $j^\text{th}$ element is bigger than the next one, they change places, and so on. This way, in the first iteration, the element with the greatest value goes to the last position $($i.e. goes to $\text{a[N]}).$ Doing the same, in the second iteration of the loop, $j$ goes from $j=1$ to $j=N-2,$ and the element of the second greatest value goes to one position before the last element $($i.e. it goes to $\text{a[N-1]}).$ The program does this process until the array is sorted.

The pseudo-code above sorts the list in an increasing order. What would you modify to make your program sort the elements in decreasing order?

---

You could simply change the third line of the pseudo-code: instead of using $\text{"if a[j]>a[j+1],"}$ you should use $\text{"if a[j]<a[j+1]"}.$ $_\square$

Here is one way to implement bubble sort in Python. There are other ways to implement the algorithm, but all implementations stem from the same ideas. Bubble sort can be used to sort any orderable list.

1
2
3
4
5
6
7
8

def bubble_sort(array):
    index = len(array) - 1
    while index >= 0:
        for j in range(index):
            if array[j] > array[j+1]:
                array[j], array[j+1] = array[j+1], array[j]
        index -= 1
    return array

To calculate the complexity of the bubble sort algorithm, it is useful to determine how many comparisons each loop performs. For each element in the array, bubble sort does $n-1$ comparisons. In big O notation, bubble sort performs $O(n)$ comparisons. Because the array contains $n$ elements, it has an $O(n)$ number of elements. In other words, bubble sort performs $O(n)$ operations on an $O(n)$ number of elements, leading to a total running time of $O\big(n^2\big)$.

Another way to analyze the complexity of bubble sort is by determining the recurrence relation that represents it.

When $i=1,$ no comparisons are made by the program. When $i=2,$ one comparison is made by the program. When $i=3,$ two comparisons are made, and so on. Thus, we can conclude that when $i=m,$ $m-1$ comparisons are made. Hence, in an array of length $n,$ it does $1+2+3+4+\cdots+(n-2)+(n-1)$ comparisons.

Note that $$\sum_{q=1}^{p} q = \frac{p(p+1)}{2}.$$ Using the previous formula to calculate $1+2+3+4+ \cdots +(n-2)+(n-1),$ it follows that $$\frac{(n-1)(n-1+1)}{2}=\frac{n(n-1)}{2}.$$ Use the master theorem to solve this recurrence for the running time. As expected, the algorithm's complexity is $O\big(n^2\big).$

Note: $O(n)$ is the best-case running time for bubble sort. It is possible to modify bubble sort to keep track of the number of swaps it performs. If an array is already in sorted order, and bubble sort makes no swaps, the algorithm can terminate after one pass. With this modification, if bubble sort encounters a list that is already sorted, it will finish in $O(n)$ time.

Though bubble sort is simple and easy to implement, it is highly impractical for solving most problems due to its slow running time. It has an average and worst-case running time of $O\big(n^2\big)$, and can only run in its best-case running time of $O(n)$ when the input list is already sorted.

Bubble sort is a stable sort with a space complexity of $O(1)$.