Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order. This algorithm is not suitable for large data sets as its average and worst-case time complexity is quite high.

How Bubble Sort Works?

Consider an array arr[] = {5, 1, 4, 2, 8}

First Pass:

Bubble sort starts with very first two elements, comparing them to check which one is greater. ( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1. ( 1 5 4 2 8 ) –> ( 1 4 5 2 8 ), Swap since 5 > 4 ( 1 4 5 2 8 ) –> ( 1 4 2 5 8 ), Swap since 5 > 2 ( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them. Second Pass:

Now, during second iteration it should look like this: ( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ) ( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), Swap since 4 > 2 ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) Third Pass:

Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted. ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

Bubble sort moves the biggest element to the right of the array in each iteration. So it is opposite to selection sort - the sorted subarray is built from the right of the array whereas selection sort builds sorted subarray from left by finding minimum element.

BubbleSort - Java implementation

Bubble Sort - Python Implementation

Output Sorted array: 1 2 4 5 8 Time Complexity: O(n2)

Space Complexity: O(1)

Optimized Implementation of Bubble Sort:

The above function always runs O(n^2) time even if the array is sorted. It can be optimized by stopping the algorithm if the inner loop didn’t cause any swap.

Optimised Bubble Sort - Java Implementation

Optimised Bubble Sort - Python Implementation

Worst Case Analysis for Bubble Sort:

The worst-case condition for bubble sort occurs when elements of the array are arranged in decreasing order. In the worst case, the total number of iterations or passes required to sort a given array is (n-1). where ‘n’ is a number of elements present in the array.

At pass 1 : Number of comparisons = (n-1) Number of swaps = (n-1)

At pass 2 : Number of comparisons = (n-2) Number of swaps = (n-2)

At pass 3 : Number of comparisons = (n-3) Number of swaps = (n-3) . . . At pass n-1 : Number of comparisons = 1 Number of swaps = 1

Now , calculating total number of comparison required to sort the array = (n-1) + (n-2) + (n-3) + . . . 2 + 1 = (n-1)*(n-1+1)/2 { by using sum of N natural Number formula } = n (n-1)/2

For the Worst case:

Total number of swaps = Total number of comparison Total number of comparison (Worst case) = n(n-1)/2 Total number of swaps (Worst case) = n(n-1)/2

Worst and Average Case Time Complexity: O(N2). The worst case occurs when an array is reverse sorted. Best Case Time Complexity: O(N). The best case occurs when an array is already sorted. Auxiliary Space: O(1)

Recursive Implementation Of Bubble Sort:

The idea is to place the largest element at their position and keep doing the same for every other elements.

Approach:

Place the largest element at their position, this operation makes sure that first largest element will be placed at the end of array. Recursively call for rest n – 1 elements with same operation and placing the next greater element at their position. Base condition for this recursion call would be, when number of elements in the array becomes 0 or 1 then, simply return (as they are already sorted). Below is the implementation of the above approach:

Recursive Bubble Sort - C++ Implementation

Recursive Bubble Sort - Python Implementation

Recursive Bubble Sort - Java Implementation

Reference: https://www.geeksforgeeks.org/bubble-sort/?ref=lbp https://www.geeksforgeeks.org/recursive-bubble-sort/