Loop Control Statements in C Introduction to HTML How to use the Github API The image tag, anchor tag and the button tag Ordered and Unordered Lists in HTML The division tag HTML Forms Tables in HTML Introduction to C Programming Introduction to Python Varibles and Datatypes in Python Operators in Python Typecasting in Python Input and Output in Python If Else in Python Loops in Python Break, Continue and Pass in Python Python practice section 1 Lists in Python Tuple in Python

Bubble Sort in Python

Sorting means arranging the elements of an array in either ascending or descending order. Bubble sort is the simplest sorting algorithm. It works by repeatedly comparing adjacent elements and swapping them if they are not in the right order.

Dry Run

When we compare adjacent elements and swap them if they are in the wrong order, then the larger element keeps pushing on the right. Hence after the first pass, the largest element reaches the rightmost position of the array. Or we can say, At the end of ith pass, the ith largest element reaches its correct position. Hence, the array becomes fully sorted by the end of N passes. 

arr= [1,5,3,8,7,2,6]

Pass 1

arr[0] < arr[2], so no swap happens, so arr remains [1,5,3,8,7,2,6]
arr[1] > arr[2], so swap arr[1] & arr[2], so arr becomes [1,3,5,8,7,2,6]
arr[2] < arr[3], so no swap happens, so arr remains [1,3,5,8,7,2,6]
arr[3] > arr[4], so swap arr[3] & arr[4], so arr becomes [1,3,5,7,8,2,6]
arr[4] > arr[5], so swap arr[4] & arr[5], so arr becomes [1,3,5,7,2,8,6]
arr[5] > arr[6], so swap arr[5] & arr[6], so arr becomes [1,3,5,7,2,6,8]

8 is the largest element so it reaches (n-1)th index by the end of the 1st pass.

Pass 2

arr[0] < arr[1], so no swap happens, so arr remains [1,3,5,7,2,6,8]
arr[1] < arr[2], so no swap happens, so arr remains [1,3,5,7,2,6,8]
arr[2] < arr[3], so no swap happens, so arr remains [1,3,5,7,2,6,8]
arr[3] > arr[4], so swap arr[3] & arr[4], so arr becomes [1,3,5,2,7,6,8]
arr[4] > arr[5], so swap arr[4] & arr[5], so arr becomes [1,3,5,2,6,7,8]

7 is the second largest element so it reaches (n-2)th index by the the end of the 2nd pass.

Pass 3

arr[0] < arr[1], so no swap happens, so arr remains [1,3,5,2,6,7,8]
arr[1] < arr[2], so no swap happens, so arr remains [1,3,5,2,6,7,8]
arr[2] > arr[3], so swap arr[2] & arr[3] , so arr becomes [1,3,2,5,6,7,8]
arr[3] < arr[4], so no swap happens, so arr remains [1,3,2,5,6,7,8]

6 is the third largest element so it reaches (n-3)th index by the end of 3the rd pass.

Pass 4

arr[0] < arr[1], so no swap happens, so arr remains [1,3,2,5,6,7,8]
arr[1] > arr[2], so swap arr[1] & arr[2], so arr becomes [1,2,3,5,6,7,8]
arr[2] < arr[3], so no swap happens, so arr remains [1,2,3,5,6,7,8]

Pass 5

arr[0] < arr[1], so no swap happens, so arr remains [1,2,3,5,6,7,8]
arr[1] < arr[2], so no swap happens , so arr remains [1,2,3,5,6,7,8]

Pass 6

arr[0] < arr[1], so no swap happens, so arr remains [1,2,3,5,6,7,8]

The array is fully sorted.

Implementation

In the first pass, we run a loop from 0 to (n-1) so that the largest element reaches the (n-1)th index. In the second pass, we run a loop from 0 to (n-2) so that the second largest element reaches the (n-2)th index, and the largest element remains at the (n-1)th index. This is done for all the elements. To repeat this process n times, we use an outer loop from 0 to n-1. 

def bubble_sort(arr):
    for i in range(0,len(arr)-1):
        for j in range(0,len(arr)-i-1):
            if arr[j]>arr[j+1]:
                arr[j],arr[j+1]=arr[j+1],arr[j]

        print(f"After pass {i+1}, arr = ",arr)
        print()

arr=[1,5,3,8,7,2,6]
print("Initial unsorted list = ",arr)
print()

bubble_sort(arr)

print("Final Sorted list = ",arr)
Output
Initial unsorted list =  [1, 5, 3, 8, 7, 2, 6]

After pass 1, arr =  [1, 3, 5, 7, 2, 6, 8]

After pass 2, arr =  [1, 3, 5, 2, 6, 7, 8]

After pass 3, arr =  [1, 3, 2, 5, 6, 7, 8]

After pass 4, arr =  [1, 2, 3, 5, 6, 7, 8]

After pass 5, arr =  [1, 2, 3, 5, 6, 7, 8]

After pass 6, arr =  [1, 2, 3, 5, 6, 7, 8]

Final Sorted list =  [1, 2, 3, 5, 6, 7, 8]

Optimized Approach

As we can see in the above example, the array was completely sorted in the 3rd pass. Still, we went through 4 more passes with the same array. We can optimize the above code such that when there is no swap in the inner loop, that means that all the elements are at their correct positions. So, we can break from the loop early. 

def bubble_sort(arr):
    for i in range(0,len(arr)-1):
        swapped=False
        for j in range(0,len(arr)-i-1):
            if arr[j]>arr[j+1]:
                swapped=True
                arr[j],arr[j+1]=arr[j+1],arr[j]
            
        if swapped==False:        # that means no swap so all the elements are at their correct positions
            break
        else:
            print(f"After pass {i+1}, arr = ",arr)
            print()

arr=[1,5,3,8,7,2,6]
print("Initial unsorted list = ",arr)
print()

bubble_sort(arr)

print("Final Sorted list = ",arr)
Output
Initial unsorted list =  [1, 5, 3, 8, 7, 2, 6]

After pass 1, arr =  [1, 3, 5, 7, 2, 6, 8]

After pass 2, arr =  [1, 3, 5, 2, 6, 7, 8]

After pass 3, arr =  [1, 3, 2, 5, 6, 7, 8]

After pass 4, arr =  [1, 2, 3, 5, 6, 7, 8]

Final Sorted list =  [1, 2, 3, 5, 6, 7, 8]
Time Complexity : O(n2)
Space Complexity : O(1) no extra space used

Time Complexity Analysis

Worst Case Complexity : O(n2)
Explanation : It occurs when the array is sorted in reverse order. In the first pass, we run a loop from j=0 to j=n-2 and compare arr[j] and arr[j+1]. Hence, there are (n-1) iterations and a total of (n-1) comparisons. After the first pass, the (n-1)th index contains the largest element. In the next pass, we run our loop from j=0 to j=n-3. Hence, there will be (n-2) iterations and a total of (n-2) comparisons.
Hence, the total number of iterations for an array of size n is:
= (n-1)+(n-2)+(n-3)+...+(n-(n-2))+(n-(n-1))+(n-n)
= (n-1)+(n-2)+(n-3)+...+2+1+0
= Sum of numbers from 1 to (n-1)
= ((n-1)+1).(n-1)/2
= n.(n-1)/2
= (n2-n)/2
Total no. of iterations = O(n2)
Total no. of comparisons = n.(n-1)/2 = O(n2)
Total no. of swaps = n.(n-1)/2 = O(n2)
So, the time complexity in the worst case will be O(n2).
Average Case Complexity : O(n2)
Explanation : It occurs when the array becomes sorted before completing N passes.
Total no. of iterations = O(n2)
Total no. of comparisons = O(n2)
Total no. of swaps = O(n2)
So, the time complexity will be O(n2).
Best Case Complexity : O(n)
Explanation: The best case occurs when the array is almost sorted or fully sorted i.e. after the first pass, the array becomes sorted.
Total no. of iterations = (n-1) = O(n)
Total no. of comparisons = (n-1) = O(n)
Total no. of swaps = (n-1) = O(n)
So, the time complexity will be O(n).

Advantages and Disadvantages

Advantages :
  1. Easy to implement and understand.
  2. Takes O(n) time when the array is already sorted.
  3. Stable algorithm i.e. the order of same elements remains the same after sorting.
  4. No additional space required.
Disadvantages :
  1. Takes O(n2) time to sort the elements. Hence, not very efficient to sort large data.
  2. It takes maximum time when the array is sorted in reverse order.