The Algorithms logo
The Algorithms
AboutDonate

Recursive Bubble Sort

D
/**
 * @file
 * @author [Aditya Prakash](https://adityaprakash.tech)
 * @brief This is an implementation of a recursive version of the [Bubble sort algorithm](https://www.geeksforgeeks.org/recursive-bubble-sort/)
 *
 * @details
 * The working principle of the Bubble sort algorithm.

 * Bubble sort is a simple sorting algorithm used to rearrange a set of ascending or descending order elements.
 * Bubble sort gets its name from the fact that data "bubbles" to the top of the dataset.
 
 * ### Algorithm

 * What is Swap?

 * Swapping two numbers means that we interchange their values.
 * Often, an additional variable is required for this operation. 
 * This is further illustrated in the following:

 * void swap(int x, int y){
 *     int z = x;
 *     x = y;
 *     y = z;
 * }

 * The above process is a typical displacement process.
 * When we assign a value to x, the old value of x is lost.
 * That's why we create a temporary variable z to store the initial value of x.
 * z is further used to assign the initial value of x to y, to complete swapping.

 * Recursion

 * While the recursive method does not necessarily have advantages over iterative
 * versions, but it is useful to enhance the understanding of the algorithm and
 * recursion itself. In Recursive Bubble sort algorithm, we firstly call the
 * function on the entire array, and for every subsequent function call, we exclude
 * the last element. This fixes the last element for that sub-array.Formally, for
 * `ith` iteration, we consider elements up to n-i, where n is the number of
 * elements in the array. Exit condition: n==1; i.e. the sub-array contains only
 * one element.

 * Complexity
 * Time complexity: O(n) best case; O(n²) average case; O(n²) worst case
 * Space complexity: O(n)

 * We need to traverse the array `n * (n-1)` times. However, if the entire array is
 * already sorted, then we need to traverse it only once. Hence, O(n) is the best case
 * complexity
*/

#include <cassert>   /// for assert
#include <iostream>  /// for IO operations
#include <vector>    /// for std::vector
#include <array>     /// for std::array
#include <algorithm> /// for std::is_sorted

/**
 * @namespace sorting
 * @brief Sorting algorithms
 */
namespace sorting {

/**
 * @brief This is an implementation of the recursive_bubble_sort. A vector is passed
 * to the function which is then dereferenced, so that the changes are
 * reflected in the original vector. It also accepts a second parameter of
 * type `int` and name `n`, which is the size of the array.
 * 
 * @tparam T type of data variables in the array
 * @param nums our array of elements.
 * @param n size of the array
 */
template <typename T>
void recursive_bubble_sort(std::vector<T> *nums, uint64_t n) {
    if (n == 1) {  //!< base case; when size of the array is 1
        return;
    }

    for (uint64_t i = 0; i < n - 1; i++) {  //!< iterating over the entire array
        //!< if a larger number appears before the smaller one, swap them.
        if ((*nums)[i] > (*nums)[i + 1]) {
            std::swap((*nums)[i], (*nums)[i + 1]);
        }
    }

    //!< calling the function after we have fixed the last element
    recursive_bubble_sort(nums, n - 1);
}
}  // namespace sorting

/**
 * @brief Self-test implementations
 * @returns void
 */
static void test() {
    // 1st example. Creating an array of type `int`.
    std::cout << "1st test using `int`\n";
    const uint64_t size = 6;
    std::vector<int64_t> arr;
    // populating the array
    arr.push_back(22);
    arr.push_back(46);
    arr.push_back(94);
    arr.push_back(12);
    arr.push_back(37);
    arr.push_back(63);
    // array populating ends

    sorting::recursive_bubble_sort(&arr, size);
    assert(std::is_sorted(std::begin(arr), std::end(arr)));
    std::cout << " 1st test passed!\n";
    // printing the array
    for (uint64_t i = 0; i < size; i++) {
        std::cout << arr[i] << ", ";
    }
    std::cout << std::endl;

    // 2nd example. Creating an array of type `double`.
    std::cout << "2nd test using doubles\n";
    std::vector<double> double_arr;

    // populating the array
    double_arr.push_back(20.4);
    double_arr.push_back(62.7);
    double_arr.push_back(12.2);
    double_arr.push_back(43.6);
    double_arr.push_back(74.1);
    double_arr.push_back(57.9);
    // array populating ends

    sorting::recursive_bubble_sort(&double_arr, size);
    assert(std::is_sorted(std::begin(double_arr), std::end(double_arr)));
    std::cout << " 2nd test passed!\n";
    // printing the array
    for (uint64_t i = 0; i < size; i++) {
        std::cout << double_arr[i] << ", ";
    }
    std::cout << std::endl;

}

/**
 * @brief Main function
 * @returns 0 on exit
 */
int main() { 
    test();  // run self-test implementations
    return 0;
}
About this Algorithm

Bubble Sort is one of the simplest sorting algorithms that compares two elements at a time and swaps them if they are in the wrong order. This process is repeated until the entire sequence is in order.

  • Time Complexity: O(n ^ 2) for average case; O(n) for best case.
  • Space Complexity: O(n); note that iterative bubble sort has space complexity as O(1).

Steps

Base case: If the size of the array is 1, return.

  • We need to fix the last element of the current sub-array. For this, iterate over the entire array using normal Bubble Sort, and perform swapping.
  • Next, call the function on the entire array excluding the last element(which was fixed by the iteration in the above step)
  • Repeat until Base Case is reached.

Example

Let the given array be: {5, 3, 2, 1, 4}

First Iteration:

  • {5, 3, 2, 1, 4} -> {3, 5, 2, 1, 4} Swap since 5 > 3
  • {3, 5, 2, 1, 4} -> {3, 2, 5, 1, 4} Swap since 5 > 2
  • {3, 2, 5, 1, 4} -> {3, 2, 1, 5, 4} Swap since 5 > 1
  • {3, 2, 1, 5, 4} -> {3, 2, 1, 4, 5} Swap since 5 > 4

This iteration has fixed the position of 5. Now, we will consider the array up to index 3.

Second Iteration:

  • {3, 2, 1, 4, 5} -> {2, 3, 1, 4, 5} Swap since 3 > 2
  • {2, 3, 1, 4, 5} -> {2, 1, 3, 4, 5} Swap since 3 > 1
  • {2, 1, 3, 4, 5}; As 3 < 4, do not swap

Note: As we check one less element with every iteration, we do not need elements at index 3 and 4 i.e., 4 and 5, as 5 is already in order. Formally, for an array with n integers, we consider elements only up to index n - i, where i is the iteration number.

Third Iteration:

  • {2, 1, 3, 4, 5} -> {1, 2, 3, 4, 5} Swap since 1 > 2
  • {1, 2, 3, 4, 5}; As 2 < 3, do not swap

Fourth Iteration:

  • {1, 2, 3, 4, 5}; As 1 < 2, do not swap

Fifth Iteration:

  • {1, 2, 3, 4, 5}; As the size of the array is 1, return.

Note: This is the base case.

Pseudo Code

void bubbleSort(arr[], n)
    if(n==1)
        return;

    for(i = 0; i<n-1; i++)
        if(arr[i] > arr[i+1])
            swap(arr[i], arr[i+1])

    bubbleSort(arr, n-1)

Implementations

Video Explanation

A video explaining iterative as well as recursive bubble sort