Prerequisites

T0 learn about Bubble Sort, you must know:

1. Python 3
2. Python data structures - Lists

What is Bubble Sort?

In the last tutorial, we saw how to search for an element from unsorted and sorted lists. We discovered that search efficiency is greater when the lists are sorted. So how do we sort a list? In this tutorial and in the tutorials to follow we are going to examine some common algorithms for list sorting. Each algorithm has its pros and cons which we will discuss as we go.

Note: All these algorithms focus on sorting the list in an ascending order (descending order is considered unsorted).

First, let's look at Bubble Sort, one of the most basic and simple algorithms. It may not be the most efficient, but it is very easy to implement. A bubble sort takes in an unsorted list and keeps comparing each element with its right side neighbour in order to sort the data. Whichever element is smaller gets shifted to the left. After completion of one round, the largest number ends up in its correct position. In other words, the largest number bubbles to the top or right in this case. Then, the process is repeated again and again until all of the data is sorted. Let us see an example to understand this better.

a = [6,8,1,3,0,5]

Round 1:

0 - 6<8 (no swap) - [6,8,1,3,0,5]

1 - 8>1 (swap) - [6,1,8,3,0,5]

2 - 8>3 (swap) - [6,1,3,8,0,5]

3 - 8>0 (swap) - [6,1,3,0,8,5]

4 - 8>5 (swap) - [6,1,3,0,5,8]

Note: 8 is in its correct place

Round 2:

0 - 6>1 (swap) - [1,6,3,0,5,8]

1 - 6>3(swap) - [1,3,6,0,5,8]

2 - 6>0(swap) - [1,3,0,6,8]

3 - 6<8 (no swap) - [1,3,0,6,8] -- not needed

Note: 6 is in its correct place

Round 3:

0 - 1<3 (no swap) - [1,3,0,6,8]

1 - 3>0 (swap) - [1,0,3,6,8]

2 - 3<6 (no swap) - [1,0,3,6,8]

3 - 6<8 (no swap) - [1,0,3,6,8] -- not needed

Note: 3 is in its correct place

Round 4:

0 - 1>0 (swap) - [0,1,3,6,8]

1 - 1<3 (no swap) - [0,1,3,6,8]

2 - 3<6 (no swap) - [0,1,3,6,8] -- not needed

3 - 6<8 (no swap) - [0,1,3,6,8] -- not needed

Note: 1 is in its correct place 

Round 5:

0 - 0<1 (no swap) - [0,1,3,6,8]

1 - 1<3 (no swap) - [0,1,3,6,8]-- not needed

2 - 3<6 (no swap) - [0,1,3,6,8]-- not needed

3 - 6<8 (no swap) - [0,1,3,6,8]-- not needed

Note: 0 is in its correct place. Even though 0 was in its correct place in round 4, our algorithm does not understand that until the process is complete.

The above unsorted list is not the worst case, the worst case unsorted list would be a list in descending order. For such a list, that contains n elements, we need to perform (n-1) swaps for it to be sorted in ascending order. Try this yourself. Observe how for the first round you need to sort all of the n elements, while on the second round you sort (n-1) elements and so on and so forth.

Trythisanimation to get a visualization of the algorithm.

How to implement Bubble Sort?

Before we go into the algorithm and code, it is important to understand how swapping works. To swap the value of two elements, a = 10 and b = 5 we need a temp variable. This variable stores the value of a temporarily which is later assigned to b.

a = 10

b = 5

temp = a  #a = 10, temp = 10, b = 5

a = b        #a = 5, temp = 10, b = 5

b = temp  #a = 5, temp = 10, b = 10

print(a) #prints 5

print(b) #prints 10

Algorithm

Now, let's look at implementing the optimized version of bubble sort:

1. For the first iteration, compare all the elements (n). For the subsequent runs, compare (n-1) (n-2) and so on.
2. Compare each element with its right side neighbour.
3. Swap the smallest element to the left.
4. Keep repeating steps 1-3 until the whole list is covered.

Code

def bubbleSort(alist):

   #Setting the range for comparison (first round: n, second round: n-1  and so on)
   for i in range(len(alist)-1,0,-1):

      #Comparing within set range
       for j in range(i):

           #Comparing element with its right side neighbor
           if alist[j] > alist[j+1]:

               #swapping
               temp = alist[j]
               alist[j] = alist[j+1]
               alist[j+1] = temp

   return alist

print(bubbleSort([5,1,2,3,9,8,0]))

This algorithm is of 0(n^2) (n to the power 2)

Conclusion

You can further optimize the above code to check if the input list is already sorted. This can be done by checking the number of swaps that happen in a given round. If no swaps are made then the list is sorted. This algorithm is apt for small lists but overall it is obviously not an efficient one. That’s it for this tutorial. Be sure to try writing this code on your own and learn about it's applications. Happy Pythoning!