Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Bubble Sort

EASYProblemSolveExternal Links

Description

You are given an array of integers. Your task is to sort the array in ascending order using the Bubble Sort algorithm.

Bubble Sort works by repeatedly stepping through the list, comparing adjacent elements, and swapping them if they are in the wrong order. The pass through the list is repeated until the list is sorted. The algorithm gets its name because smaller elements gradually "bubble" to the top (beginning) of the list, while larger elements "sink" to the bottom (end).

You must modify the array in-place — no extra array should be created for the output.

Examples

Example 1

Input: arr = [4, 1, 3, 9, 7]

Output: [1, 3, 4, 7, 9]

Explanation: Starting with [4, 1, 3, 9, 7], bubble sort compares adjacent pairs and swaps when the left element is larger than the right. After multiple passes through the array — where the largest unsorted element is pushed to its correct position in each pass — the array becomes fully sorted as [1, 3, 4, 7, 9].

Example 2

Input: arr = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

Output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Explanation: This is the worst case for bubble sort — the array is in complete reverse order. Every adjacent pair is out of order in the first pass, requiring the maximum number of swaps. It takes n-1 = 9 full passes to completely sort the array.

Example 3

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

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

Explanation: The array is already sorted. A basic bubble sort would still make all passes without swapping anything. An optimized version can detect that no swaps occurred in the first pass and terminate early.

Constraints

  • 1 ≤ arr.size() ≤ 10^3
  • 1 ≤ arr[i] ≤ 10^3

Editorial

Brute Force

Intuition

Imagine you have a row of people standing in line, and you want to arrange them by height from shortest to tallest. You start at the beginning of the line and compare the first two people. If the taller person is standing before the shorter one, you ask them to swap places. Then you move one step forward and compare the next pair. You keep doing this until you reach the end of the line.

After your first walk through the entire line, the tallest person is guaranteed to be standing at the very end — because every time they were compared with someone shorter, they swapped forward. But the rest of the line may still be out of order.

So you walk through again, but this time you only need to go up to the second-to-last position (since the last one is already correct). You repeat this process, and with each pass, the next tallest person settles into their correct position. After enough passes, everyone is in order.

This is the essence of bubble sort — the largest elements "bubble up" to the end of the array one pass at a time.

Step-by-Step Explanation

Let's trace through with arr = [4, 1, 3, 9, 7]:

Pass 1 (i=0): Place the largest element at the end

Step 1: Compare arr[0]=4 and arr[1]=1. Since 4 > 1, swap them.

  • Array becomes: [1, 4, 3, 9, 7]

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

  • Array becomes: [1, 3, 4, 9, 7]

Step 3: Compare arr[2]=4 and arr[3]=9. Since 4 < 9, no swap needed.

  • Array stays: [1, 3, 4, 9, 7]

Step 4: Compare arr[3]=9 and arr[4]=7. Since 9 > 7, swap them.

  • Array becomes: [1, 3, 4, 7, 9]
  • 9 is now at its correct position (index 4).

Pass 2 (i=1): Place the second largest element

Step 5: Compare arr[0]=1 and arr[1]=3. Since 1 < 3, no swap.

  • Array stays: [1, 3, 4, 7, 9]

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

  • Array stays: [1, 3, 4, 7, 9]

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

  • Array stays: [1, 3, 4, 7, 9]
  • 7 is confirmed at its correct position (index 3).

Pass 3 (i=2): Place the third largest element

Step 8: Compare arr[0]=1 and arr[1]=3. No swap.

Step 9: Compare arr[1]=3 and arr[2]=4. No swap.

  • 4 is confirmed at its correct position (index 2).

Pass 4 (i=3): Final pass

Step 10: Compare arr[0]=1 and arr[1]=3. No swap.

  • All elements are in their correct positions.

Result: [1, 3, 4, 7, 9]

Bubble Sort — Swapping Adjacent Elements Pass by Pass — Watch how bubble sort compares adjacent pairs and swaps them when out of order, pushing the largest unsorted element to its correct position in each pass.

Algorithm

  1. Run an outer loop from i = 0 to n-2 (this controls the number of passes)
  2. For each pass, run an inner loop from j = 0 to n-i-2 (each pass considers one fewer element at the end since the largest elements are already sorted)
  3. Inside the inner loop, compare arr[j] with arr[j+1]
  4. If arr[j] > arr[j+1], swap them
  5. After all passes complete, the array is sorted

Code

class Solution {
public:
    void bubbleSort(vector<int>& arr) {
        int n = arr.size();
        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]);
                }
            }
        }
    }
};
class Solution:
    def bubbleSort(self, arr):
        n = len(arr)
        for i in range(n - 1):
            for j in range(n - i - 1):
                if arr[j] > arr[j + 1]:
                    arr[j], arr[j + 1] = arr[j + 1], arr[j]
class Solution {
    public void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            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;
                }
            }
        }
    }
}

Complexity Analysis

Time Complexity: O(n²)

The outer loop runs n-1 times. For each iteration i, the inner loop runs n-i-1 times. Total comparisons: (n-1) + (n-2) + ... + 1 = n(n-1)/2, which is O(n²). This is the case regardless of whether the input is sorted, reverse-sorted, or random — the basic version always does all passes.

Space Complexity: O(1)

Bubble sort is an in-place algorithm. We only use a constant amount of extra space for the loop variables and a temporary variable during swaps. No auxiliary arrays or data structures are needed.

Why This Approach Is Not Efficient

The basic bubble sort always performs all n-1 passes, even if the array becomes sorted before all passes are completed. Consider the array [1, 2, 3, 4, 5] — it is already sorted, yet the basic version still performs (n-1) + (n-2) + ... + 1 comparisons.

The key observation is: if a complete pass through the array produces zero swaps, the array is already sorted and we can stop immediately. In the trace above, after Pass 1 the array happened to be sorted, but the basic algorithm continued with Pass 2, 3, and 4 unnecessarily.

This insight leads to an optimized version that can achieve O(n) best-case time complexity for already-sorted or nearly-sorted arrays, compared to the basic version's O(n²) in all cases.

Optimal Approach - Optimized Bubble Sort with Early Termination

Intuition

Think back to our line of people being sorted by height. If you walk the entire line comparing adjacent pairs and find that nobody needs to swap, that means everyone is already standing in the correct order. There is no point in walking through the line again.

We can add a simple flag — call it swapped — that we set to false at the start of each pass. If we perform any swap during the pass, we set it to true. At the end of the pass, if swapped is still false, we know the array is fully sorted and we can break out of the outer loop immediately.

This optimization does not change the worst-case time complexity (a reverse-sorted array still needs all passes), but it dramatically improves the best case from O(n²) to O(n) — a single pass with zero swaps confirms the array is sorted.

Step-by-Step Explanation

Let's trace through with arr = [4, 1, 3, 9, 7]:

Pass 1 (i=0): swapped = false

Step 1: Compare arr[0]=4 and arr[1]=1. 4 > 1 → swap. swapped = true.

  • Array: [1, 4, 3, 9, 7]

Step 2: Compare arr[1]=4 and arr[2]=3. 4 > 3 → swap. swapped = true.

  • Array: [1, 3, 4, 9, 7]

Step 3: Compare arr[2]=4 and arr[3]=9. 4 < 9 → no swap.

  • Array: [1, 3, 4, 9, 7]

Step 4: Compare arr[3]=9 and arr[4]=7. 9 > 7 → swap. swapped = true.

  • Array: [1, 3, 4, 7, 9]
  • End of Pass 1. swapped = true, so we continue.

Pass 2 (i=1): swapped = false

Step 5: Compare arr[0]=1 and arr[1]=3. 1 < 3 → no swap.

  • Array: [1, 3, 4, 7, 9]

Step 6: Compare arr[1]=3 and arr[2]=4. 3 < 4 → no swap.

  • Array: [1, 3, 4, 7, 9]

Step 7: Compare arr[2]=4 and arr[3]=7. 4 < 7 → no swap.

  • Array: [1, 3, 4, 7, 9]
  • End of Pass 2. swapped = false → the array is already sorted!

Step 8: Break out of the outer loop. No need for Pass 3 or Pass 4.

Result: [1, 3, 4, 7, 9] — we saved 2 unnecessary passes compared to the basic version.

Optimized Bubble Sort — Early Termination with Swapped Flag — Watch how the swapped flag allows the algorithm to detect when the array is already sorted and stop early, saving unnecessary passes.

Algorithm

  1. Run an outer loop from i = 0 to n-2
  2. At the start of each pass, set swapped = false
  3. Run an inner loop from j = 0 to n-i-2:
    • Compare arr[j] with arr[j+1]
    • If arr[j] > arr[j+1], swap them and set swapped = true
  4. After the inner loop completes, check the swapped flag:
    • If swapped is false, break out of the outer loop (array is sorted)
    • If swapped is true, continue to the next pass
  5. The array is now sorted

Code

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):
        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:

  • Worst Case: O(n²) — When the array is in reverse order, every pass requires swaps and the swapped flag is always true. We perform all n-1 passes, doing (n-1) + (n-2) + ... + 1 = n(n-1)/2 comparisons.
  • Best Case: O(n) — When the array is already sorted, the first pass performs n-1 comparisons with zero swaps. The swapped flag remains false, and we break immediately after one pass.
  • Average Case: O(n²) — For a randomly ordered array, we typically need O(n) passes with O(n) comparisons each.

Space Complexity: O(1)

We only added one boolean variable (swapped) compared to the basic version. The algorithm remains in-place with constant extra space.