In this post we’ll see how to write Bubble sort program in Python. Bubble sort is considered the simplest sorting algorithm out of the three simpler sorting algorithms bubble sort, insertion sort and selection sort. Bubble sort is considered the slowest too because of a proportionally large number of swaps along with the comparisons.
How does Bubble sort work
In Bubble sort adjacent elements are compared and swapped if element at left is greater than element at right. For example if n[0] and n[1] are compared and n[0] > n[1] then n[0] and n[1] are swapped. Then you move by one index and compare the adjacent elements i.e. n[1] and n[2].
By the end of first pass you should have the maximum element in the list at the rightmost position. Since the maximum element bubbles up to the top thus the name Bubble sort.
To sum up the steps for bubble sort-
- Compare the adjacent elements.
- If element at the left is greater than the element at the right then swap the elements.
- Move one position right. Start from point 1.
In the next pass again you start from the two leftmost elements and compare the elements and swap if required. Since the rightmost element is already in its sorted position so this pass runs till (N-1) elements.
For example if you have an array [5, 3, 8, 2] then in the first pass-
Iteration 1- Initially 5 is compared with 3, since 5 (element at left) is greater than 3 (element at right), elements are swapped making the array [3, 5, 8, 2].
Iteration 2- Move to next position and compare element at index 1 and index 2 (5 and 8), since 5 is not greater than 8 so swapping is not done and array remains [3, 5, 8, 2].
Iteration 3- Again move over one position and compare 8 and 2. Since 8 is greater than 2, elements are swapped giving us the array as [3, 5, 2, 8].
As you can see by the end of first pass the maximum element is at the rightmost position. In the next pass last element is not included in the comparison as it is already at its final position so the array that is considered for comparison and swapping effectively becomes [3, 5, 2].
Bubble Sort Python program
def bubble_sort(nlist):
list_length = len(nlist)
# reduce length by 1 in each pass
for i in range(list_length-1, 0, -1):
for j in range(i):
# compare
if nlist[j] > nlist[j+1]:
# swap elements
nlist[j+1], nlist[j] = nlist[j], nlist[j+1]
nlist = [47, 85, 62, 34, 7, 10, 92, 106, 2, 54]
print('Original List-', nlist)
bubble_sort(nlist)
print('Sorted List-', nlist)
Output
Original List- [47, 85, 62, 34, 7, 10, 92, 106, 2, 54] Sorted List- [2, 7, 10, 34, 47, 54, 62, 85, 92, 106]
Time and Space complexity of Bubble sort
In Bubble sort (N-1) comparisons are required in the first pass, (N-2) comparisons in the second pass, (N-3) comparisons in the third pass and so on.
So the total number of comparisons is- N(N-1)/2
Thus the time complexity of Bubble sort is O(n2).
Bubble sort is an in-place sorting algorithm and doesn’t require any auxiliary space so the space complexity of Bubble sort is O(1).
That's all for this topic Bubble Sort Program in Python. If you have any doubt or any suggestions to make please drop a comment. Thanks!
>>>Return to Python Programs Page
Related Topics
You may also like-
