In this article, we will be discussing the Python Bubblesort Algorithm in complete detail. We will start with it’s explanation, followed by a complete solution which is then explained by breaking it down into steps and explaining each of them separately.
At the end we have also included a small comparison of the Python Bubblesort with others similar algorithms. As a bonus, we also have a video explanation of the Bubblesort Algorithm, which is included at the very end of the article.
Methodology:
The simplest kind of sort, that is often taught to beginners. It involves swapping two values in a list if the preceding value is greater than the next one. Two (nested) for loops are set up, which iterate through the entire list of values, making the above comparison, and swapping values if required.
Big O notation: n2
Best Case: n (When values are already sorted)
Bubble Sort Solution
In Bubblesort, we basically make passes over the array. The number of passes is n - 1, where n is the number of elements in the array. The first for loop is responsible for making n – 1 number of passes. The second for loop is incharge of making comparisons between the elements in the array.
Whether you do arr[j] > arr[j + 1] or arr[j + 1] < arr[j] doesn’t make a different. You just need to make a comparison between the current number, and next one which executes the swap is the next number is smaller.
def bubbleSort(arr):
n = len(arr)
for i in range(n-1):
for j in range(0, n-i-1):
if arr[j] > arr[j+1] :
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
if __name__ == "__main__":
array = [3, 6, 1, 2, 8, 4, 6]
print(bubbleSort(array))
Once the two for loops have completed their iterations, the function will return the now-sorted array.
for j in range(0, n-i-1):
The reason for setting up the second for loop like this, is an optimization trick because as you sort the array, the number of required comparisons per pass will decrease. If you pay attention to the index numbers in the worked example in the next section, you will realize this yourself.
The reason for the “-1” in the second for loop is that when we compare two elements, we will do j and j + 1, meaning that we will be comparing the last element anyway. Not including this will throw an error, because if you reach the last index and then look for j + 1, it won’t exist.
Here is a more simpler, but unoptimized bubble sort algorithm. I decided to include it here so you could compare the two, and deepen your understanding.
def bubbleSort(arr):
n = len(arr)
for i in range(n-1):
for j in range(0, n-1):
if arr[j] > arr[j+1] :
temp = arr[j]
arr[j]= arr[j+1]
arr[j + 1] = temp
return arr
if __name__ == "__main__":
array = [3, 6, 1, 2, 8, 4, 6]
print(bubbleSort(array))
The creation of an extra variable temp, is nessacery to store the value of either one of the two values being swapped, else it would be overwritten.
BubbleSort Explanation (Worked Example)
We’ll begin with this small array of 7 numbers, and show the complete bubble sort process, step by step.
The image below shows us the bubble sort in it’s initial stage. i and j are both 0, and the jth is pointing to the first value, and j + 1 is pointing to the second. We will now be comparing the two values, and swapping if nessacery.
As 8 is larger than 3, we will not be swapping. Instead, we will increment j, as the for loop progresses.
We now have j pointing to the value 8, and j + 1 pointing to 1. Since 8 is larger than 1, this means that the two values are not in sorted order. Hence we will swap the two.
We then proceed like we were before. Since 8 and 9 are in sorted order, we will continue on.
At j = 3, and j + 1 = 4 we find another situation where a swap is required, between 9 and 4, resulting in the below image.
And once again, we swap the values 9 and 6, as we continue through the second for loop. We are still in the first pass of the first for loop, hence i is zero.
We then swap 9 and 2, as the last comparison in the first pass of the first for loop.
We are now in the second pass of the i for loop, and i = 1. We can already see that our array looks a bit more sorted that it was at the start.
We will now swap 3 and 1, resulting in the below image.
We will continue on, till we find the next positions to be swapped, which are 8 and 2, and then 6 and 8.
This marks the end of the second pass of the i for loop. Our array is almost completely sorted, with just a few more swaps required.
The Image contains both the steps for the 3rd and 4th pass in the bubble sort algorithm.
After these two swaps, we now have a completely sorted array with us.
Recursive Bubblesort Algorithm
The concept and swapping is almost the exact same as the iterative version of the Python BubbleSort Algorithm. The only difference is that the Recursion calls and the if statement at the start of the function take the place of the first for loop from earlier.
The recursive calls keep decreasing the value of n, and the if statement breaks it once it reaches 1.
def bubbleSort(arr, n):
if (n <= 1):
return arr
for j in range(0, n-1):
if arr[j] > arr[j+1] :
temp = arr[j]
arr[j]= arr[j+1]
arr[j + 1] = temp
bubbleSort(arr, n - 1)
return arr
if __name__ == "__main__":
array = [3, 6, 1, 2, 8, 4, 6]
print(bubbleSort(array, len(array) - 1))
And of course, remember to pass in that extra parameter in the bubblesort function.
Video Tutorial
Here we you can watch the video version of this article. If you are having trouble understanding, or still have some doubts, be sure to check this out. It’s a more interactive experience which will definitely help you.
Interested in learning about other algorithms in Python? Follow the link!
This marks the end of the Python BubbleSort Algorithm. Any suggestions or contributions for CodersLegacy are more than welcome. Questions regarding the tutorial content can asked in the comments section below.