Introduction to Bubble Sort in Python
Bubble sort is a simple and logical sorting algorithm. Its working principle is based on recursively swapping adjacent elements if the order is incorrect. In this topic, we are going to learn about Bubble Sort in Python.
Bubble sort sometimes also referred to as Sinking sort, Ripple sort.
Let’s see it through an example:
(6 1 4 3) -> (1 6 4 2): Here 1st two elements get swapped if the order is not correct.
(1 6 4 2) -> (1 4 6 2): Here the next two elements get swapped if the order is not correct.
(1 4 6 2) -> (1 4 2 6): Here the next two elements get swapped if the order is not correct.
(1 4 2 6)-> (1 4 2 6): Here 1st two elements get compared, but didn’t swap as the order is correct.
4.8 (4,344 ratings)
(1 4 2 6)-> (1 2 4 6): Here the next two elements get swapped, as the order was not correct.
(1 2 4 6) -> (1 2 4 6): Here last two elements get compared, but didn’t swap as the order is
Now we know the array looks sorted, however, one run is required without any swap, to the algorithm to know if sorting is done.
(1 2 4 6) -> (1 2 4 6) : No swap in1st two elements.
(1 2 4 6) -> (1 2 4 6): No swap in next two elements.
(1 2 4 6) -> (1 2 4 6) : No swap in last two elements.
As no swaps occurred at any stage, now the algorithm understands sorting is perfect.
Bubble sort has got its name because elements move up into the correct order which is like bubbles rising to the surface.
Bubble sort in Python Language
Now let’s see the logical implementation of bubble sort through python. Python is a very widely used language these days. Understanding it through python will surely give you the confidence to be able to write it any other languages as well.
m = len(arr)
# Traverse through all the array elements
for u in range(m):
for v in range(0, m-u-1):
# traverse the array from 0 to m-u-1
# Swap if the element is greater than adjacent next one
if arr[v] > arr[v+1] :
arr[v], arr[v+1] = arr[v+1], arr[v]
To print array after bubble sort you need follow code:
for i in range(len(arr)):
Here arr will be your array.
Explanation of Python code
Here “m” is the length of the array. Two for loops hold the actual ground logic, where “u” represents the first element while “v” represents the second with which the first element has to compared for swapping if sort order between both is not correct.
“arr[v] > arr[v+1]” this represents the comparison of consecutive elements, if first element is greater than second element, exchange operation will be performed by following expression:
That is “arr[v], arr[v+1] = arr[v+1], arr[v]”.
This exchange operation is called swap. The good part is no temporary memory is required for this kind of swap operation.
“u” represents the loop of every run, while “v” represents stages of every stage. An example in the above section can be referred to.
After performing bubble sort, one can see the sorted array, with code mentioned below:
for i in range(len(arr)):
print ("%d" %arr[i]),
Let’s see how this behaves in Python IDE, for a deeper understanding:
There are a few facts about Bubble Sort, which everyone should know before implementing it:
- A bubble sort is often considered as a not good efficient sorting method. As it has to exchange the items until its final location is known. This all leads to wastage of operations and hence very costly. This algorithm passes through each and every element, where sorting required or not required. Once the run passes without any swap, bubble sort is considered as completed.
- This is the simplest among all data structures, for any beginner this gives good confidence. It’s easy to construct and understand.
- It uses a lot of time and memory.
- This is considered a stable algorithm, as it preserves the relative order of elements.
- Considered good for small array/list. However, its a bad idea to use it for long ones.
Going through the above content of bubble sort, one could have got crystal clear understanding of this sorting algorithm, specialized with python. Once, one gets comfortable with logic of bubble sort, understanding the other set of data structures will then be easier. A logical approach is the only way to excel in the field of data structure. Understanding first the logic of data structure algorithm at every stage and then targeting its code through Python or in any other language should be the way.
This is a guide to Bubble Sort in Python. Here we discuss the logical implementation of bubble sort through python code with the explanation. You may also look at the following article to learn more –