Algorithms and Data Structures in Python: Bubble Sort and its Optimization

Introduction

Sorting is one of the most basic algorithm types and it appears quite often in interview. Among them, bubble sort is probably the most fundamental one. The naive bubble sort is usually not that efficient, however, it’s important to understand how it works and how it can be optimized.

Naive Bubble Sort

Native bubble sort used a nested loop to iterate through the target array, and swap each pair of adjacent elements if arr[i] < arr[i + 1], so that the largest element always merge to the top(last of the array).

Implement Naive Bubble Sort in Python

As you’ve seen from the code snippet above, this sorting function operates on the original array instead of creating a new one:

In the outer loop, we simply iterate through the array while in the inner loop, we compare each pair of element and swap if the first one is larger than the second. Since we already print out some step in the code, now let’s check how the function run own this array:

-----iteration:0-----
Now compare: 4 and 1
Swap!
Now compare: 4 and 2
Swap!
Now compare: 4 and 10
Now compare: 10 and 3
Swap!
Now compare: 10 and 7
Swap!
-----iteration:1-----
Now compare: 1 and 2
Now compare: 2 and 4
Now compare: 4 and 3
Swap!
Now compare: 4 and 7
Now compare: 7 and 10
-----iteration:2-----
Now compare: 1 and 2
Now compare: 2 and 3
Now compare: 3 and 4
Now compare: 4 and 7
Now compare: 7 and 10
-----iteration:3-----
Now compare: 1 and 2
Now compare: 2 and 3
Now compare: 3 and 4
Now compare: 4 and 7
Now compare: 7 and 10
-----iteration:4-----
Now compare: 1 and 2
Now compare: 2 and 3
Now compare: 3 and 4
Now compare: 4 and 7
Now compare: 7 and 10
-----iteration:5-----
Now compare: 1 and 2
Now compare: 2 and 3
Now compare: 3 and 4
Now compare: 4 and 7
Now compare: 7 and 10

[4, 1, 2, 10, 3, 7]: To sort an array with the length of 6, this function runs 6 iterations and in the end, while all the element is compared and merged to the top (if necessary), the sorting process completed.

It’s pretty obvious that this bubble sort function has a time complexity of O(n²) since it runs on a nested loop base.

Is there a way to improve the performance a little bit?

Optimized Bubble Sort

One way to optimize bubble sort is to skip some of the swaps: If the swaps didn’t occur in an entire iteration, doesn’t that mean all the elements in this array is already in order?

In the optimized version of bubble sort, a flag variable no_swaps is declared, in each iteration, if no swap happens, the function will stop and return the current array.

Now let’s see how the function run on the same arry:

-----iteration:0-----
Now compare: 4 and 1
Swap!
Now compare: 4 and 2
Swap!
Now compare: 4 and 10
Now compare: 10 and 3
Swap!
Now compare: 10 and 7
Swap!
-----iteration:1-----
Now compare: 1 and 2
Now compare: 2 and 4
Now compare: 4 and 3
Swap!
Now compare: 4 and 7
Now compare: 7 and 10
-----iteration:2-----
Now compare: 1 and 2
Now compare: 2 and 3
Now compare: 3 and 4
Now compare: 4 and 7
Now compare: 7 and 10
All sorted, no need to swap any more

As you can see from above, it stops in only three iteration as by then the arrya is already sorted.