Algorithm

Bubble Sort

Sorting Pattern

Bubble Sort

Given an unsorted array of integers, sort the array in ascending order using the Bubble Sort algorithm. The sorting should be done in-place.

CONSTRAINTS
  • 1 ≤ nums.length ≤ 500
  • -100 ≤ nums[i] ≤ 100
  • Space Complexity: O(1)
  • Time Complexity: O(N²) average
EXAMPLE 1
Input: nums = [5, 1, 4, 2, 8]
Output: [1, 2, 4, 5, 8]
In each pass, the largest remaining element 'bubbles up' to its correct position at the end.
EXAMPLE 2
Input: nums = [1, 2, 3, 4, 5]
Output: [1, 2, 3, 4, 5]
The array is already sorted. An optimized Bubble Sort can detect this in one pass (O(N)).
EXAMPLE 3
Input: nums = [5, 4, 3, 2, 1]
Output: [1, 2, 3, 4, 5]
Reverse sorted input is the worst-case scenario, requiring the maximum number of swaps.
Should the array be sorted in-place, or should I return a new one?
Please perform the sort in-place to minimize memory usage.
How should we handle duplicate elements?
Duplicate elements should remain in their original relative positions after sorting.
Is there a specific range for the input integers?
They can range from -100 to 100, and the array size will not exceed 500 elements.
The Idea

Think of it like bubbles in water: the largest values are "heavier" and sink to the end of the array one by one. In each pass, we compare adjacent neighbors and swap them if they are in the wrong order.

Pseudo Code
text
FOR i from 0 to N-1:
    swapped = false
    FOR j from 0 to N-i-2:
        IF array[j] > array[j+1]:
            SWAP(array[j], array[j+1])
            swapped = true
    IF not swapped: BREAK  // Optimization
Walkthrough:[5, 1, 4, 2]
- Pass 1: [5, 1, 4, 2] → [1, 5, 4, 2] → [1, 4, 5, 2] → [1, 4, 2, 5]. (5 is now in place).
- Pass 2: [1, 4, 2, 5] → [1, 4, 2, 5] → [1, 2, 4, 5]. (4 is now in place).
- Pass 3: [1, 2, 4, 5]. No swaps occurred! Array is sorted.
Key Traits

- Stability: Yes (equal elements are never swapped).
* In-Place: Yes (O(1) extra space).
- Time Complexity: O(N²) average, O(N) best case (already sorted).

Interactive Strategy Visualization

Visual Intuition

Watch the bubble sort process step-by-step.

5
0
3
1
8
2
4
3
2
4
STEP 1 / 23 • INIT

Starting Bubble Sort on a random array.

O(N²) Naive Bubble Sort
→
O(N) Optimized (Best Case)