Bubble Sort Program in Python

Bubble sort is a sorting algorithm that uses the swapping of elements to sort the list in either ascending or descending order. Bubble sort is the simplest and easy-to-understand sorting algorithm. In this article, we will learn more about bubble sort, the bubble sort algorithm in python, and the time and space complexity of the bubble sort program in python.

What is Bubble Sort Python?

The bubble sort algorithm compares adjacent elements and swaps them to sort the list. The bubble sort uses two for loops to sort the list. The first for loop (outer for loop) is used to traverse the list n times. The Second for loop (inner for loop) is used to traverse the list and swap elements if necessary.

Bubble Sort Algorithm Python:-

Let’s understand how the bubble sort algorithm python works using an example and visualizing the algorithm. The process of sorting the list in ascending using the bubble sort algorithm python is given below.

Now Let’s see how n-1 (n=size of a list) list passes work on a list.

First pass (i=0)

  • First, we will run the inner loop for n-i-1 (5-0-1 = 4) times and we will compare each adjacent pair.
  • For j=0, compare j=0 (l[0]=4) and j+1=1 (l[1]=3) here l[j]>l[j+1] so we will swap two elements because we want higher elements on the right side to sort a list.
  • For j=1, l[1] (4) < l[2] (9) so we will not swap elements because the higher element (9) is already on the right side.
  • For j=2, l[2] (9) > l[3] (1) so we will swap elements.
  • For j=3, l[3] (9) > l[4] (5) so we will swap elements.
  • After performing the first pass we can see that the last element of a list (9) is already at its right position so in further passes we will not touch that element.

Second pass (i=1)

  • In the second pass (i=1), we will run inner loop n-i-1 time ( 5-1-1 =3) which one less than the first pass it is because the last element is already sorted in the second pass so we will not consider the last element.
  • For j=0, l[0] (3) < l[1] (4) so we will not swap elements.
  • For j=1, l[1] (4) > l[2] (1) so we will swap elements.
  • For j=2, l[2] (4) < l[3] (5) so we will not swap elements
  • After the completion of the second pass, we can see that the last two elements of an list ( [5,9] ) are in their right position.

Third pass (i=2)

  • In the third pass ( i=2 ), we will run the inner loop n-i-1 (5-2-1 = 2) times.
  • For j=0, l[0] (3) > l[1] (1) so we will swap elements.
  • For j=1, l[1] (3) < l[2] (4) so we will not swap elements.
  • After performing the third pass we can see that the last three elements ( [4,5,9] ) are in their right positions.

Fourth pass (i=3)

  • In the fourth pass (i=3 ), we will run the inner loop n-i-1 (5-3-1=1) times.
  • For j=0, l[0] (1) < l[1] (3) so we will not swap elements.
  • After performing the fourth pass we can see that our list is sorted.

Sorting happens in place in bubble sort python which means if there are two elements with the same values so after performing the bubble sort program in python the order of that two elements will be the same. Let’s understand this with an example list= [4,6,3,6,5] here two same elements are 6 at index 2 and 4 now after performing bubble sort list= [3,4,5,6,6] now two elements which is same are 6 at index 4 and 5 so element 6 at index 4 is element 6 at index 2 before performing sorting and element 6 at index 5 is the element at index 4 before performing sorting.

Bubble Sort Program in Python:-

def bubble_sort(list1):   
    for i in range(0,len(list1)-1):  
        for j in range(len(list1)-1):  
            if(list1[j]>list1[j+1]):  
                temp = list1[j]  
                list1[j] = list1[j+1]  
                list1[j+1] = temp  
    return list1  
  
list1 = [5, 3, 8, 6, 7, 2]  
print("The unsorted list is: ", list1)  
print("The sorted list is: ", bubble_sort(list1))

Output

The unsorted list is:  [5, 3, 8, 6, 7, 2]
The sorted list is:  [2, 3, 5, 6, 7, 8]

There is one problem with the above bubble sort program in python when a given list is already sorted the above program will still finish all the two loops so the time complexity becomes O(n^2) though the list is already sorted. Let’s see how can we optimize the above bubble sort program in python.

Optimized Bubble Sort Program in Python:-

We can observe one thing if our list is already sorted then no swap will be performed so we can use this observation to write an optimized bubble sort program in python.

def bubble_sort(list1):  
    has_swapped = True  
  
    while(has_swapped):  
        has_swapped = False  
        for i in range(len(list1) - 1):  
            if list1[i] > list1[i+1]:  
                # Swap  
                list1[i], list1[i+1] = list1[i+1], list1[i]  
                has_swapped = True  
    return list1  
  
list1 = [5, 3, 8, 6, 7, 2]  
print("The unsorted list is: ", list1)  
print("The sorted list is: ", bubble_sort(list1))

Time Complexity Analysis of Bubble Sort Python

Best:- O(n) when the given list is already sorted at that time program using only one loop.
Average:- O(n^2) when the given list is not sorted.
Worst:- O(n^2) when the given list is reverse sorted at that time we have to perform a swap for each comparison. So the total swaps performed will be n*(n-1)/2

Auxiliary Space complexity of bubble sort python

Auxiliary space complexity:- O(1) it’s because we are not using any extra list to perform bubble sort python. We are only using variables so the space complexity is O(1) to perform the bubble sort algorithm python.

Other Python Programs
Python program to reverse a number
Python program for heap sort
Python program to check armstrong number
Python program to check leap year
Python program to convert celsius to fahrenheit
Python program to find factorial of a number
Python program to reverse a linked list
Python Program to find the middle of a linked list using only one traversal
Python Program to Add Two Numbers
Python Program to Check Palindrome Number
Python Program to Print the Fibonacci Series
Python Loop Program
Anagram Program in Python

Leave a Reply

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