Bubble Sort Algorithm in Python

Bubble sort, also known as sinking sort, is based on the concept of swapping the adjacent elements of the list/array if they are in the wrong order. As the name suggests, the smaller elements “bubble” to the top of the list. The swapping of the adjacent elements is repeated until no more swap is needed. Although the algorithm seems very simple, it’s too slow esp. when all the elements are in decreasing order and it’s required to arrange them in ascending order.

For example, suppose 2nd element is 8 and the 1st element is 9, then the position of these two elements will be exchanged. Then 3rd element will be compared with 2nd element and so on. The below python code is for bubble sort algorithm and I have put the output of each step to show how does the algorithm work.

def swap(a1,a2):
	x = a1
	a1 = a2
	a2 = x
	return(a1,a2)
	
def bubble_sort(a):
	n = len(a)
	finished = 0
	while (finished != 1):
		swapped = 0
		for i in xrange(1,n):
			if(a[i-1] > a[i]):
				(a[i-1],a[i]) = swap(a[i-1],a[i])
				swapped = 1
		n = n-1
		print a
		if (swapped == 0):
			finished = 1
	return a

l = [25,24,21,21,20,1,1,9,10,8,3,4,5,1,3,1]
s = bubble_sort(l)
#print s

The output of the above code is as follows…

[24, 21, 21, 20, 1, 1, 9, 10, 8, 3, 4, 5, 1, 3, 1, 25]
[21, 21, 20, 1, 1, 9, 10, 8, 3, 4, 5, 1, 3, 1, 24, 25]
[21, 20, 1, 1, 9, 10, 8, 3, 4, 5, 1, 3, 1, 21, 24, 25]
[20, 1, 1, 9, 10, 8, 3, 4, 5, 1, 3, 1, 21, 21, 24, 25]
[1, 1, 9, 10, 8, 3, 4, 5, 1, 3, 1, 20, 21, 21, 24, 25]
[1, 1, 9, 8, 3, 4, 5, 1, 3, 1, 10, 20, 21, 21, 24, 25]
[1, 1, 8, 3, 4, 5, 1, 3, 1, 9, 10, 20, 21, 21, 24, 25]
[1, 1, 3, 4, 5, 1, 3, 1, 8, 9, 10, 20, 21, 21, 24, 25]
[1, 1, 3, 4, 1, 3, 1, 5, 8, 9, 10, 20, 21, 21, 24, 25]
[1, 1, 3, 1, 3, 1, 4, 5, 8, 9, 10, 20, 21, 21, 24, 25]
[1, 1, 1, 3, 1, 3, 4, 5, 8, 9, 10, 20, 21, 21, 24, 25]
[1, 1, 1, 1, 3, 3, 4, 5, 8, 9, 10, 20, 21, 21, 24, 25]
[1, 1, 1, 1, 3, 3, 4, 5, 8, 9, 10, 20, 21, 21, 24, 25] – Final output

One comment

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.