Sorting is a way to rearrange or reorder a data in ascending or descending order. Sometimes we need to sort a data to process it quickly or use it efficiently.
Bubble sort is one of the simplest and easiest sorting algorithms to sort data items stored in a data structure like list. Bubble sort works by comparing all the elements with their adjacent elements one by one and sort them based on their values.
In bubble sort, sorting takes place by comparing adjacent data items one by one and swapping each pair that is out of order.
This algorithm is called bubble sort, because with each iteration the largest data item in the list bubbles up towards the last place in the list, just like a water bubble rises up to the water surface.
In this article, We will understand bubble sort in python with its working. We will also see python code for bubble sort.
For better understanding we just take a list L with total N number of elements stored in it. These elements in list are not sorted in particular order and we need to sort it with bubble sort.
Bubble sort works in iterations and passes. There are total N – 1 passes and in each pass, there is a comparison of all elements with its adjacent element to sort full list. After each pass the largest element will be bubble up at the last position. So after N-1th pass the largest N-1 elements will be sorted, hence the smallest first element will be sorted by default and we do not need to perform Nth pass for first element and need to stop algorithm to run for performing one additional pass, obviously, to optimize the algorithm.
Moreover, as after each pass one element is going to be sorted and hence does not require comparison with its adjacent element which reduces one iteration after every consecutive passes. That means, in first pass it requires N – 1 comparisons and in 2nd pass it requires N – 2 comparisons and so on.
Working of 1st Pass
Now, we will understand the working of first pass with its iterations. In below figure, we have shown first pass with all its N-1 iterations.
In first iteration, we start by comparing the first two data items of the list. If the first data item is larger than the second data item, we need to swap these two data items. If they are already in correct order (ascending) we need to leave them as it is. We then move to the next iteration with next pair of data items, compare their values with each other and swap them if they are not in ascending order. This process continues N-1 times that is to the last pair of data items in the list.
In above figure, we can see, after first pass of algorithm the largest data item 93 is bubbled up and placed at last position. As 93 is sorted and hence does not required to compare it with its adjacent item in next pass which reduces one iteration in 2nd pass.
As we have discussed, Bubble sort require N – 1 passes to completely sort a list, the above process need to be repeated for N – 1 times and after each pass one element will be sorted and placed at its correct sorted order. So here after N – 1 = 8 passes, array will be sorted.
As bubble sort is working by comparing and swapping each element with its adjacent element in a list in all its N – 1 passes, it requires to perform total N ^ 2 comparisons in a list to sort it. Therefore, if we have a list of total N elements then time complexity of bubble sort is O(N^2).
Large time complexity of Bubble sort algorithm is its main disadvantage. Because of worst case complexity of bubble sort algorithm is O(N^2), a lot more time it takes to sort a list with having huge number of elements. Thus bubble sort is more suitable for teaching sorting algorithms instead of real python applications.
It is concluded that, Bubble sort in python is one of the easiest technique to sort a list, but with having more time complexity. It is a stable and in-place algorithm which is most used for introducing the concept of sorting algorithms. Bubble sort is also used in computer graphics because of its feature to detect the minute errors and fix them in linear time.
Other Important Topics:
- Python and Other Object-Oriented Programming Languages
- Python 2 vs Python 3
- Introduction to Python Programming
- The Basic Elements of Python Programming
- Branching, Indentation, Looping and Control Structure in Python
- Indexing & Slicing of Strings and Capturing Inputs
- Built-in Data Types and Functions in Python
- Specifications, Global Variables, Modules and Packages in Python
- Working with Files in Python
- Strings in Python
- Lists in Python
- Tuples in Python
- Dictionaries in Python
- Mutable and Immutable Python Objects
- Functions as Objects, map(), filter() and reduce()
- Exception Handling in Python
- Classes and Object Oriented Programming in Python
- Searching Algorithms in Python
- Method Resolution Order (MRO) in Python
- Sorting Algorithms in Python