Bubble Sort Algorithm in Python

In this article, we will briefly discuss what bubble sort algorithms in python is, how to implement it in python, its working, and complexity.

The Bubble Sort algorithm is a simple sorting method that iterates through a given list, compares every pair of neighboring items, and exchanges them if they are out of order. This process is repeated until the list is sorted, which occurs when no further exchanges are necessary.

Here’s the basic pseudocode for the bubble sort algorithm:

The bubble sort algorithm has the advantage of being easy to understand and implement.

Implementing Bubble Sort Algorithm

The below-given steps can be used to implement bubble sort in a programming language:

1. Create a function that takes an array or a list of elements as an argument.
2. Get the length of the list.
3. Create a loop that repeats until no more swaps are needed.
4. Create an inner loop that steps through the list, comparing each pair of adjacent elements.
5. If the elements are in the wrong order, swap them.
6. Set a flag swapped to true if any swaps were made during the inner loop.
7. After the inner loop, if the swapped flag is false, the list is sorted, and you can break the outer loop.
8. Repeat the inner and outer loops until the list is sorted.
9. Return the sorted list.

What is Programming	What is Python
What is Data Science	What is Machine Learning

Working of Bubble Sort

Now let’s understand the working of Bubble sort algorithm with the help of an example.

Let’s say we need to sort the list [-5, 54, 0, 22, -14] using bubble sort in ascending order. To do so follow the below steps:

First Iteration:

1. Start from index 0 and compare it to the element at index 1.
2. Now compare if the element at 0 index is greater than the element at index 1.  
3. If yes, swap the element at the 0 index with the element at index 1.
4. If no, continue iterating through the upcoming elements in the list.
5. This will continue till the last element of the list has been evaluated.

Second Iteration:

At the end of the first iteration, our original list has been updated to [-5, 0, 22, -14, 54]. Now repeat the steps followed in the first iteration till the end of the list, as the list is not completely sorted yet. Take a look at the below image for reference.

Third Iteration:

At the end of the second iteration, our original list has been updated to [-5, 0, -14, 22, 54]. Now repeat the steps followed in the first iteration. Take a look at the below image for reference.

Fourth Iteration:

At the end of the third iteration, the updated list becomes [-5, -14, 0, 22, 54]. Our list is still not sorted. Therefore we do the process again as shown in the below image:

At this point, we have successfully managed to sort the original list ([-5, 0, 22, -14, 54]) into a sorted list ([-14, -5, 0, 22, 54]).

Programming Online Courses and Certification	Python Online Courses and Certifications
Data Science Online Courses and Certifications	Machine Learning Online Courses and Certifications

Implementing Bubble Sort Algorithm in Python

A basic implementation of the bubble sort algorithm in Python is given below:

This implementation will sort the list arr in ascending order using the bubble sort algorithm. The output should be:

So in the above code, we have taken the following steps to implement the bubble sort algorithm in python:

• A function bubble_sort is defined that takes a list arr as an input.
• The length of the list n is calculated using the len() function.
• An outer loop is created with range(n) that repeats n times.
• An inner loop is created with range(0, n-i-1) that iterates over the list arr from the first element to the second-to-last element.
• Within the inner loop, a comparison is made between each pair of adjacent elements using the if statement. If the elements are in the wrong order, they are swapped using tuple unpacking.
• The inner loop repeats until all elements have been compared and possibly swapped.
• The outer loop repeats until no more swaps are needed, indicating that the list is sorted.
• The sorted list is finally returned.

Complexity Analysis:

Time Complexity: O(N^2)

Space Complexity: O(1)

The time complexity of the bubble sort algorithm implemented in the above code is O(n^2). This means that the time it takes to sort the list grows quadratically with the size of the list.

In the best-case scenario, when the list is already sorted, the algorithm will still need to perform n comparisons for each element, for a total of n * (n-1) / 2 comparisons, which results in a time complexity of O(n^2).

In the worst case scenario, when the list is sorted in the reverse order, the algorithm will perform n comparisons for each element, for a total of n * (n-1) / 2 comparisons, and will also need to make n swaps, resulting in a time complexity of O(n^2).

The space complexity of the bubble sort algorithm is O(1), as the algorithm sorts the list in place and does not use any additional memory.

Now that we have made familiar with the basic implementations of the bubble sort algorithm, let’s take a look at few other ways of implementing the same.

Recursive Implementation Bubble Sort Algorithm in Python

We can make use of the following steps to recursively implement Bubble sort in python:

• Define a function bubble_sort(arr, n) where arr is the array to be sorted and n is the size of the array.
• If n is equal to 1, return the array as it is already sorted.
• Traverse through the array from the beginning to the second last element.
• If the current element is greater than the next element, swap them.
• Call the function bubbleSort(arr, n-1) recursively.
• Return the sorted array.

Recursive Implementation:

Given below is a recursive implementation of bubble sort in Python:

Output:

Complexity Analysis:

Time Complexity: O(N^2)

Space Complexity: O(N)

The time complexity of the recursive implementation of Bubble Sort is O(n^2), where n is the size of the input array.

In each recursive call, the function makes one full pass through the array to compare and swap adjacent elements if they are in the wrong order. In the worst-case scenario, where the input array is in reverse order, the function will need to make n-1 passes in the first call, n-2 in the second call, and so on until it makes a single pass in the last call.

The total number of comparisons and swaps in the worst case is the sum of the first n-1 integers, which is (n-1)*n/2, giving an upper bound of O(n^2) time complexity.

The space complexity of the recursive implementation of Bubble Sort is O(n), where n is the size of the input array.

The function uses the call stack to store intermediate states of the array as it recurses through the function calls. In the worst case, where the input array is in reverse order, the function will need to make n-1 calls, each storing a copy of the array with one more element in its correct place. The size of each copy is the same as the input array, giving a total space complexity of O(n).

Note: The above implementation is not efficient for large input sizes or for arrays that are already mostly sorted, as it will still make n^2 comparisons even when the array is already sorted. Other sorting algorithms, such as Merge Sort or Quick Sort, may be more appropriate in those cases.

Conclusion

In this article, we have briefly discussed what bubble sort algorithm in python is, how to implement it in python, its working.

hope you will like the article.

Keep Learning!!

Keep Sharing!!