In this article, we are going to understand the various implementations of the Bubble Sort Algorithm and primarily comprehend the subtle difference between implementing recursively and recursive implementation.

Bubble Sort is a classic sorting algorithm which focusses on making the largest element in the array, settle at the right most correct position at the end of each iteration. Within n-1 iterations, all the elements are moved to their right positions via successive adjacent swaps.

1. Naive Iterative Implementation

void bubbleSort(int *arr, int n) {
    for(int i = 0; i < n - 1; i++) {
        for(int j = 0; j < n - i - 1; j++) {
            if(arr[j] > arr[j + 1])
                swap(arr[j], arr[j + 1]);
        }
    }
}

We simply use 2 for loops, the outer for loop is used to indicate the size of the array to be considered.
At the end of each iteration, we decrease the size of the array by 1 since the largest element is settled at the right most position. The inner for loop is used for successive adjacent swaps and is used to make the largest element settle down at its correct position.
However, there is a huge drawback, especially considering the case where the input array is already sorted.
Our algorithm will continue to check the condition for swapping elements for all the n-1 iterations.

2. Enhanced Iterative Implementation

We can clearly observe, if no swaps take place in a particular iteration, it indicates that all the elements in the array are placed at their correct positions.
When such a situation is encountered, we could break the outer for loop.

void bubbleSort_iter(int *arr, int n) {
    for(int i = 0; i < n - 1; i++) {
        bool flag = true;
        for(int j = 0; j < n - i - 1; j++) {
            if(arr[j] > arr[j + 1]) {
                flag = false;
                swap(arr[j], arr[j + 1]);
            }
        }
        // one iteration is over
        if(flag) 
            break;
    }
}

Using 2 for loops, we were successfully able to write an algorithm for Bubble sort using iterative implementation.

Let's now look at the recursive implementation and understand the subtle difference between implementing recursively and recursive implementation as stated in the beginning of this article.

3. Implementing Recursively

void bubbleSort(int *arr, int n) {
    // base case
    if(n == 1)
        return;

    // recursive calls
    for(int j = 0; j < n - 1; j++) {
        if(arr[j] > arr[j + 1])
            swap(arr[j], arr[j + 1]);
    } 
    bubbleSort(arr, n - 1);
}

This is the most common solution that strikes the mind when we are asked to implement recursively.
In the above code, we are implementing the outer for loop recursively, by making a recursive call to the function with reduced array size.
However, the inner for loop stays the same, following the iterative approach.
Well this is the most easiest way to come up with a hybrid implementation of both recursion and iteration.
Coming up with a pure recursive solution, would require the removal of the inner for loop's iterative implementation and accommodating it in the recursive function calls.

4. Recursive Implementation 💯

void bubbleSort_rec(int *arr, int j, int n) {
    // base case
    if(n == 1)
        return;
    // corner edge case, end of one iteration
    if(j == n - 1)
        return bubbleSort_rec(arr, 0, n - 1);

    if(arr[j] > arr[j + 1])
        swap(arr[j], arr[j + 1]);
    // call for the next swap in the same iteration
    bubbleSort_rec(arr, j + 1, n);
}

The variable j controls the inner for loop for successive adjacent swaps whereas variable n controls the size of the array or we could rather say, the iterations.

Here, we have 2 base cases, n == 1, indicating 1 element and hence demands no sorting, j == n - 1 which marks the end of the current iteration.

We can closely observe, there are 2 recursive calls with slight variation in the parameter updations.

bubbleSort_rec(arr, 0, n - 1) makes a function call for the next iteration of the algorithm, indicating the largest element is settled at its correct position in the current iteration. Hence, the variable j is initialized back to 0 and the size of the problem is decreased by 1.

bubbleSort_rec(arr, j + 1, n) actually makes a function call for the next element in the current iteration. Hence the value of the variable j is increased by 1 and the problem size says the same.

Coming up with the above solution, at the first attempt would be less intuitive for beginners. With consistent efforts and regular practice, you can master these concepts efficiently.

Following is the full code of the implementation in C++

#include <iostream>
using namespace std;

void bubbleSort_iter(int *arr, int n) {
    for(int i = 0; i < n - 1; i++) {
        bool flag = true;
        for(int j = 0; j < n - i - 1; j++) {
            if(arr[j] > arr[j + 1]) {
                flag = false;
                swap(arr[j], arr[j + 1]);
            }
        }
        // one iteration is over
        if(flag) 
            break;
    }
}

void bubbleSort(int *arr, int n) {
    // base case
    if(n == 1)
        return;

    // recursive calls
    for(int j = 0; j < n - 1; j++) {
        if(arr[j] > arr[j + 1])
            swap(arr[j], arr[j + 1]);
    } 
    bubbleSort(arr, n - 1);
}

void bubbleSort_rec(int *arr, int j, int n) {
    // base case
    if(n == 1)
        return;
    // corner edge case, end of one iteration
    if(j == n - 1)
        return bubbleSort_rec(arr, 0, n - 1);

    if(arr[j] > arr[j + 1])
        swap(arr[j], arr[j + 1]);
    // call for the next swap in the same iteration
    bubbleSort_rec(arr, j + 1, n);
}   

int main() {
    int n;
    cin >> n;

    int arr[n];
    for(int i = 0; i < n; i++)
        cin >> arr[i];

    bubbleSort_rec(arr, 0, n);

    for(int i = 0; i < n; i++)
        cout << arr[i] << " ";

    return 0;
}

Hope you enjoyed this article and feel free to connect with me on LinkedIn and github.

To have a much better understanding of recursion, try to implement the enhanced iterative approach using recursion !