Understanding the Logic Behind Bubble Sort

Bubble sort is based on various iterations, called passes. For a list of size N, bubble sort will have N-1 passes. Let's focus on the first iteration: pass one.

The goal of pass one is pushing the highest value to the top of the list. We will see the highest value of the list bubbling its way to the top as pass one progresses.

Bubble sort compares adjacent neighbor values. If the value at a higher position is higher in value than the value at a lower index, we exchange the values. This iteration continues until we reach the end of the list. This is shown in the following diagram:

Let's now see how bubble sort can be implemented using Python:

#Pass 1 of Bubble Sort
lastElementIndex = len(list)-1 
print(0,list) 
for idx in range(lastElementIndex):                 
                    if list[idx]>list[idx+1]:                                                                             list[idx],list[idx+1]=list[idx+1],list[idx]                                         
print(idx+1,list)

If we implement pass one of bubble sort in Python, it will look as follows:

Once the first pass is complete, the highest value is at the top of the list. The algorithm next moves on to the second pass. The goal of the second pass is to move the second highest value to the second highest position in the list. To do that, the algorithm will again compare adjacent neighbor values, exchanging them if they are not in order. The second pass will exclude the top element, which was put in the right place by pass one and need not be touched again.

After completing pass two, the algorithm keeps on performing pass three and so on until all the data points of the list are in ascending order. The algorithm will need N-1 passes for a list of size N to completely sort it. The complete implementation of bubble sort in Python is as follows:

Now let's look into the performance of the BubbleSort algorithm.