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 the 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 Python code below is for the bubble sort algorithm, and I have put the output of each step to show how the algorithm works.
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]