Bubble sort | Iterative & Recursive

Given an array of integers, sort it using bubble sort algorithm.

 
 

Bubble sort is a stable, in-place sorting algorithm that is named for the way smaller or larger elements “bubble” to the top of the list. Although the algorithm is simple, it is too slow and impractical for most problems even when compared to insertion sort and is not recommended when n is large.

The only significant advantage that bubble sort has over most other implementations, even quicksort, but not insertion sort, is that the ability to detect if the list is already sorted. When the list is already sorted (best-case), the complexity of bubble sort is only O(n).

How it works?

Each pass of bubble sort steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order. At the end of each pass, the next largest element will “Bubble” up to its correct position. These passes through the list are repeated until no swaps are needed, which indicates that the list is sorted. In worst case, we might end up making n – 1 passes where n is the size of the input.

              3     5     8     4     1     9    -2 
pass 1        3     5     4     1     8    -2     9
pass 2        3     4     1     5    -2     8     9
pass 3        3     1     4    -2     5     8     9
pass 4        1     3    -2     4     5     8     9
pass 5        1    -2     3     4     5     8     9
pass 6       -2     1     3     4     5     8     9

 
Detailed illustration on how each pass works can be seen here.

The bubble sort algorithm can be easily optimized by observing that the n-th pass finds the n-th largest element and puts it into its final place. So, the inner loop can avoid looking at the last n-1 items when running for the n-th time. Another optimization would be to stop the algorithm when the inner loop didn’t do any swap.

 
Iterative C++ implementation –
 

Download   Run Code

Output:

-2 1 3 4 5 8 9

 
Recursive C++ implementation –
 

Download   Run Code

Output:

-2 1 3 4 5 8 9

 

Worst case time complexity of bubble sort is O(n2). The worst case happens when the array is reverse sorted.

Best case time complexity of bubble sort is O(n). The best case happens when the array is already sorted and the algorithm is modified to stop running when the inner loop didn’t do any swap. The optimized implementation can be seen here.

Auxiliary space used by it is O(1).

 
References: https://en.wikipedia.org/wiki/Bubble_sort

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz