Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Bubble Sort with Recursion

EASYProblemSolveExternal Links

Description

Given an array of integers, sort the array in ascending order using the Recursive Bubble Sort algorithm.

Bubble Sort works by repeatedly comparing adjacent elements and swapping them if they are in the wrong order. After each complete pass through the array, the largest unsorted element "bubbles up" to its correct position at the end.

In the recursive version, instead of using nested loops, we replace the outer loop with a recursive call. Each recursive call performs one pass of bubble sort (placing the largest element at the end), then recurses on the remaining unsorted portion of the array.

Return the sorted array.

Examples

Example 1

Input: arr = [64, 34, 25, 12, 22, 11, 90]

Output: [11, 12, 22, 25, 34, 64, 90]

Explanation: The algorithm performs multiple passes. In the first pass, 90 (already the largest) bubbles to the end. In the second pass, 64 bubbles to the second-last position. This continues until the entire array is sorted in ascending order.

Example 2

Input: arr = [5, 1, 4, 2, 8]

Output: [1, 2, 4, 5, 8]

Explanation: Pass 1 moves 8 to the end: [1, 4, 2, 5, 8]. Pass 2 moves 5 to position 3: [1, 2, 4, 5, 8]. The array is now sorted, so no further swaps are needed.

Example 3

Input: arr = [1, 2, 3, 4, 5]

Output: [1, 2, 3, 4, 5]

Explanation: The array is already sorted. The first pass makes zero swaps, so the algorithm terminates early without any changes. This is the best-case scenario.

Constraints

  • 1 ≤ arr.length ≤ 10^3
  • -10^5 ≤ arr[i] ≤ 10^5

Editorial

Brute Force

Intuition

The most straightforward way to sort an array is the iterative bubble sort approach using two nested loops.

Imagine you are organizing a line of students by height. You start from the left and compare each pair of neighbors. If the taller student is on the left, you swap them. After walking the entire line once, the tallest student will have moved all the way to the right end — they "bubbled up" through each swap.

You then repeat this walk for the remaining unsorted students (ignoring those already placed at the end). Each walk places one more student in their correct position. After enough walks, the entire line is sorted.

The outer loop controls how many passes we make, and the inner loop does the actual comparisons and swaps within each pass.

Step-by-Step Explanation

Let's trace through with arr = [5, 1, 4, 2, 8]:

Pass 1 (i=0): Sort the first 5 elements, place the largest at index 4

Step 1: Compare arr[0]=5 and arr[1]=1. Since 5 > 1, swap → [1, 5, 4, 2, 8]

Step 2: Compare arr[1]=5 and arr[2]=4. Since 5 > 4, swap → [1, 4, 5, 2, 8]

Step 3: Compare arr[2]=5 and arr[3]=2. Since 5 > 2, swap → [1, 4, 2, 5, 8]

Step 4: Compare arr[3]=5 and arr[4]=8. Since 5 < 8, no swap → [1, 4, 2, 5, 8]

After Pass 1: 8 is at its correct position (index 4).

Pass 2 (i=1): Sort the first 4 elements, place the second-largest at index 3

Step 5: Compare arr[0]=1 and arr[1]=4. Since 1 < 4, no swap → [1, 4, 2, 5, 8]

Step 6: Compare arr[1]=4 and arr[2]=2. Since 4 > 2, swap → [1, 2, 4, 5, 8]

Step 7: Compare arr[2]=4 and arr[3]=5. Since 4 < 5, no swap → [1, 2, 4, 5, 8]

After Pass 2: 5 is at its correct position (index 3). No more swaps needed — optimized version detects this and terminates.

Result: [1, 2, 4, 5, 8]

Iterative Bubble Sort — Adjacent Swaps — Watch how adjacent elements are compared and swapped, causing the largest unsorted element to bubble to the end in each pass.

Algorithm

  1. Set n = length of the array
  2. For each pass i from 0 to n-2:
    a. Set a flag swapped = false
    b. For each index j from 0 to n-i-2:
    • Compare arr[j] with arr[j+1]
    • If arr[j] > arr[j+1], swap them and set swapped = true
      c. If swapped is still false after the inner loop, the array is already sorted — break early
  3. Return the sorted array

Code

#include <vector>
using namespace std;

class Solution {
public:
    void bubbleSort(vector<int>& arr) {
        int n = arr.size();
        for (int i = 0; i < n - 1; i++) {
            bool swapped = false;
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr[j], arr[j + 1]);
                    swapped = true;
                }
            }
            if (!swapped) break;
        }
    }
};
class Solution:
    def bubbleSort(self, arr: list[int]) -> None:
        n = len(arr)
        for i in range(n - 1):
            swapped = False
            for j in range(n - i - 1):
                if arr[j] > arr[j + 1]:
                    arr[j], arr[j + 1] = arr[j + 1], arr[j]
                    swapped = True
            if not swapped:
                break
class Solution {
    public void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            boolean swapped = false;
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }
            if (!swapped) break;
        }
    }
}

Complexity Analysis

Time Complexity: O(n²)

In the worst case (reverse-sorted array), the outer loop runs n-1 times and the inner loop runs up to n-1, n-2, ..., 1 times respectively. Total comparisons = n(n-1)/2, which simplifies to O(n²).

In the best case (already sorted array), the optimization flag detects zero swaps in the first pass and terminates early, giving O(n).

Space Complexity: O(1)

The iterative version uses only a few auxiliary variables (i, j, swapped, temp). No extra data structures are allocated, so space usage is constant regardless of input size.

Why This Approach Is Not Efficient

While the iterative bubble sort works correctly, it has two drawbacks worth discussing:

  1. O(n²) Time Complexity: With n up to 10³, the worst case requires roughly 500,000 comparisons. Although this is manageable for the given constraints, bubble sort is vastly outperformed by O(n log n) algorithms like merge sort or quick sort for larger inputs.

  2. No Recursive Structure: The iterative approach uses explicit nested loops. In many educational and interview settings, the problem specifically asks for a recursive implementation to test understanding of how recursion can replace iteration. The iterative version doesn't demonstrate this concept.

The key insight for the recursive version: notice that the outer loop simply repeats the same "one pass" operation on progressively smaller subarrays. Instead of a loop, we can make a recursive call — each call performs one pass, then calls itself with n-1 (since the largest element is already in place).

This transformation teaches a fundamental pattern: any iterative process that reduces the problem size by a fixed amount after each iteration can be converted to tail recursion.

Optimal Approach - Recursive Bubble Sort

Intuition

The recursive version of bubble sort replaces the outer loop with a recursive call. The core observation is simple:

  1. One pass of bubble sort compares and swaps adjacent elements from the start to the end of the unsorted portion. After this pass, the largest element in the unsorted portion is guaranteed to be at its correct final position.

  2. After one pass on n elements, the problem reduces to sorting the first n-1 elements (since the last one is already placed correctly).

  3. This reduction is a perfect fit for recursion: perform one pass, then recursively sort the smaller subarray.

Think of it like stacking books. You go through the shelf once, each time pushing a heavier book to the right past lighter ones. After one full sweep, the heaviest book is at the far right. Now you call a friend to do the same thing, but they only need to handle the remaining books (ignoring the heaviest one you already placed). Your friend calls another friend for an even smaller section, and so on.

The base case is when the array size reduces to 1 — a single element is already sorted.

We also add an early termination optimization: if a pass completes without any swaps, the array is already sorted and we can stop recursing immediately.

Step-by-Step Explanation

Let's trace through with arr = [5, 1, 4, 2, 8]:

Recursive Call 1: bubbleSort(arr, n=5)

Step 1: Compare arr[0]=5 and arr[1]=1. Since 5 > 1, swap → [1, 5, 4, 2, 8]. Count = 1.

Step 2: Compare arr[1]=5 and arr[2]=4. Since 5 > 4, swap → [1, 4, 5, 2, 8]. Count = 2.

Step 3: Compare arr[2]=5 and arr[3]=2. Since 5 > 2, swap → [1, 4, 2, 5, 8]. Count = 3.

Step 4: Compare arr[3]=5 and arr[4]=8. Since 5 < 8, no swap → [1, 4, 2, 5, 8].

Pass done. 3 swaps occurred. Element 8 is now fixed at index 4. Since swaps happened, recurse with n=4.

Recursive Call 2: bubbleSort(arr, n=4)

Step 5: Compare arr[0]=1 and arr[1]=4. Since 1 < 4, no swap → [1, 4, 2, 5, 8].

Step 6: Compare arr[1]=4 and arr[2]=2. Since 4 > 2, swap → [1, 2, 4, 5, 8]. Count = 1.

Step 7: Compare arr[2]=4 and arr[3]=5. Since 4 < 5, no swap → [1, 2, 4, 5, 8].

Pass done. 1 swap occurred. Element 5 is now fixed at index 3. Since swaps happened, recurse with n=3.

Recursive Call 3: bubbleSort(arr, n=3)

Step 8: Compare arr[0]=1 and arr[1]=2. Since 1 < 2, no swap → [1, 2, 4, 5, 8].

Step 9: Compare arr[1]=2 and arr[2]=4. Since 2 < 4, no swap → [1, 2, 4, 5, 8].

Pass done. 0 swaps occurred. The early termination optimization kicks in — since no swaps were made, the array is already sorted. No further recursion needed.

Result: [1, 2, 4, 5, 8]

Recursive Bubble Sort — Pass-by-Pass with Recursion — Watch how each recursive call performs one bubbling pass and then reduces the problem size by 1, until the array is sorted or no swaps occur.

Algorithm

  1. Base Case: If n equals 1, return (a single element is already sorted)
  2. Perform one pass of bubble sort:
    a. Initialize a swap counter to 0
    b. For each index j from 0 to n-2:
    • If arr[j] > arr[j+1], swap them and increment the counter
  3. Early termination: If the swap counter is 0, the array is sorted — return without recursing
  4. Recursive call: Call bubbleSort(arr, n-1) to sort the first n-1 elements (the largest is already at position n-1)

Code

#include <vector>
using namespace std;

class Solution {
public:
    void bubbleSort(vector<int>& arr, int n) {
        // Base case: single element is already sorted
        if (n == 1) return;

        int count = 0;
        // One pass: bubble the largest to position n-1
        for (int j = 0; j < n - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                count++;
            }
        }

        // If no swaps occurred, array is sorted
        if (count == 0) return;

        // Recurse on the first n-1 elements
        bubbleSort(arr, n - 1);
    }

    void bubbleSort(vector<int>& arr) {
        bubbleSort(arr, arr.size());
    }
};
class Solution:
    def bubbleSort(self, arr: list[int], n: int = None) -> None:
        if n is None:
            n = len(arr)

        # Base case: single element is already sorted
        if n == 1:
            return

        count = 0
        # One pass: bubble the largest to position n-1
        for j in range(n - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                count += 1

        # If no swaps occurred, array is sorted
        if count == 0:
            return

        # Recurse on the first n-1 elements
        self.bubbleSort(arr, n - 1)
class Solution {
    public void bubbleSort(int[] arr, int n) {
        // Base case: single element is already sorted
        if (n == 1) return;

        int count = 0;
        // One pass: bubble the largest to position n-1
        for (int j = 0; j < n - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                count++;
            }
        }

        // If no swaps occurred, array is sorted
        if (count == 0) return;

        // Recurse on the first n-1 elements
        bubbleSort(arr, n - 1);
    }

    public void bubbleSort(int[] arr) {
        bubbleSort(arr, arr.length);
    }
}

Complexity Analysis

Time Complexity: O(n²)

The recursion depth is at most n-1 (one level per pass). At each level, the inner loop performs n-k-1 comparisons where k is the recursion depth. Total comparisons: (n-1) + (n-2) + ... + 1 = n(n-1)/2 = O(n²). This is identical to the iterative version.

In the best case (already sorted), the first pass detects zero swaps and terminates immediately, giving O(n) time.

Space Complexity: O(n)

Unlike the iterative O(1) space version, the recursive version uses O(n) auxiliary space due to the recursion call stack. In the worst case, we make n-1 recursive calls, each adding a frame to the stack. This is the main trade-off: the recursive version uses more memory than the iterative one.

This makes the iterative version generally preferred in practice, but the recursive version is valuable for understanding how recursion maps to iteration and for educational purposes.