Bubble Sort in Python

What is Bubble Sort ?

This is a very simple or basic algorithm to arrange elements in a particular order. This algorithm compares repeatedly the adjacent elements of list and swap them if they are not in order. This process of comparing adjacent elements continue until the complete list is sorted.

Steps of Bubble Sort for increasing order:

1. Compare first element of list with second element.
2. Swap the numbers if first number is greater than second number.
3. Compare second element with third element and swap them if they are not in order.
4. This process is repeated till last element of list

The above point completes the first step of bubble sort. After first step the last element will reach at the end of the list. for example we have the following list.

First pass in Bubble Sort

L = [12, 29, 13, 23, 2]

After first comparison the list become as given below (12 is smaller than 29 so no swapping takes place)

L = [12, 29, 13, 23, 2]

After second comparison the list become as given below (29 is greater than 13 so swapping takes place)

L = [12, 13, 29, 23, 2]

After third comparison the list become as given below (29 is greater than 23 so swapping takes place)

L = [12, 13, 23, 29, 2]

After fourth comparison the list become as given below (29 is greater than 2 so swapping takes place)

L = [12, 13, 23, 2, 29]

NOTE : After completing the above step largest element is at the end of the list.
The same step to be done by (n-1) time. Where n is the total number of elements in the list.

Second pass in Bubble Sort

After first comparison the list become as given below (12 is smaller than 13 so no swapping takes place)

L = [12, 13, 23, 2, 29]

After Second comparison the list become as given below (13 is smaller than 23 so no swapping takes place)

L = [12, 13, 23, 2, 29]

After third comparison the list become as given below (23 is greater than 2 so swapping takes place)

L = [12, 13, 2, 23, 29]

NOTE : After completing the second pass second largest element reached at its position.

Third pass in Bubble Sort

After first comparison the list become as given below (12 is smaller than 13 so no swapping takes place)

L = [12, 13, 2, 23, 29]

After second comparison the list become as given below (13 is smaller than 2 so swapping takes place)

L = [12, 2, 13, 23, 29]

NOTE : After completing the third pass third largest element reached at its position.

Fourth pass

After first comparison the list become as given below (12 is greater than 2 so swapping takes place)

L = [2, 12, 13, 23, 29]

NOTE : After completing the fourth pass fourth largest element reached at its position.

Since there are 5 elements in the list so maximum covering (5 – 1 =) 4 passes the list will be sorted.

Bubble Sort Program

Q1. Write a program to arrange the list in increasing order using bubble sort.

L = [12, 29, 13, 23, 2]

n=len(L)

for i in range(n-1):

     for j in range(n-i-1):

         if L[j] > L[j+1]:

              L[j], L[j+1] = L[j+1], L[j]

print("Sorted list is : ",L)

OUTPUT :

[2, 12, 13, 23, 29]

Q2. Write a program to arrange the list in decreasing order using bubble sort.

L = [12, 29, 13, 23, 2]

n=len(L)

for i in range(n-1):

     for j in range(n-i-1):

         if L[j] < L[j+1]:

              L[j], L[j+1] = L[j+1], L[j]

print("Sorted list is : ",L)

OUTPUT :

[29, 23, 13, 12, 2]

Q3. Write the status of the given list after first pass of bubble sort for arranging elements in increasing order.

L = [12, 25, 5, 21, 40, 3]

Ans. After first pass the list will be :

L = [12, 5, 21, 25, 3, 40]

Q4. Write the status of the given list after second pass of bubble sort for arranging elements in increasing order.

L = [12, 25, 5, 21, 40, 35]

Ans. After second pass the list will be :

L = [5, 12, 21, 3, 25, 40]

Q5. __________ will be the last element of list arranged in ascending order using bubble sort after first pass. (Largest/Smallest)

Ans. Largest

Q6. How many times the outer loop will execute in bubble sort for given list.

L = [34, 54, 22, 12, 40, 30]

Ans. 5 times

Q7. Write the three elements from the last of the list L = [34, 54, 22, 12, 40, 30] after fourth pass of bubble sort for arranging elements in increasing order.

Ans. Last three elements will be : 34, 40, 54

Disclaimer : I tried to explain the concept of bubble sort in simple language as well as the correct code of the program. If you feel that there is some error in the above article, please send me the correct code/word/spelling at csiplearninghub@gmail.com so that i can correct it and also share your valuable feedback.