Bubble Sort

Concept

Bubble Sort is the simplest sorting algorithm. It is heavily used in computer science classrooms to introduce the concept of sorting, but it is almost never used in professional software engineering due to its catastrophic $O(N^2)$ time complexity.

The algorithm loops through the array, comparing adjacent pairs of elements. If they are in the wrong order, it swaps them. By doing this repeatedly, the absolute largest element naturally “bubbles” all the way up to the very end of the array.

The Mechanism

Array: [5, 3, 8, 4, 2]

Pass 1:

• Compare 5 and 3. Wrong order! Swap. [3, 5, 8, 4, 2]
• Compare 5 and 8. Correct order.
• Compare 8 and 4. Wrong order! Swap. [3, 5, 4, 8, 2]
• Compare 8 and 2. Wrong order! Swap. [3, 5, 4, 2, 8]
  Notice that the largest number (8) is now permanently locked into its correct position at the very end.

Pass 2:
We repeat the exact same process from the beginning, but we completely ignore the final index because 8 is already locked. The 5 will bubble to the end.

Implementation

// Time Complexity: O(N^2) Worst/Average, O(N) Best (if already sorted)
// Space Complexity: O(1) In-Place

function bubbleSort(nums: number[]): number[] {
    const n = nums.length;
    let isSwapped: boolean;

    // The outer loop determines how many elements we have locked into place
    for (let i = 0; i < n; i++) {
        isSwapped = false; // Optimization flag

        // The inner loop does the bubbling.
        // We do not need to check the last 'i' elements, because they are already sorted!
        for (let j = 0; j < n - i - 1; j++) {
            
            // If the left element is larger than the right element...
            if (nums[j] > nums[j + 1]) {
                // SWAP!
                [nums[j], nums[j + 1]] = [nums[j + 1], nums[j]];
                isSwapped = true;
            }
        }

        // OPTIMIZATION: If we went through an entire inner loop and NEVER swapped anything,
        // it means the entire array is already perfectly sorted! We can break early.
        if (!isSwapped) {
            break;
        }
    }

    return nums;
}

Why it’s Terrible

Bubble Sort requires multiple nested loops just to move a single element to the end.
If the array is perfectly reverse sorted [5, 4, 3, 2, 1], it requires $(N-1) + (N-2) + (N-3)...$ comparisons, which is the mathematical sum $N(N-1)/2$, dropping the $O(N^2)$ atomic bomb.
Sorting an array of 100,000 numbers with Bubble Sort takes several minutes. Quick Sort does it in a fraction of a millisecond.

Interview Questions

Q: Is Bubble Sort Stable?
A: Yes. If we compare [5A, 5B], our if (nums[j] > nums[j+1]) statement evaluates 5 > 5 as False. They are not swapped. Therefore, identical elements will perfectly retain their original relative order.

Q: An interviewer asks you to write a sorting algorithm that detects if an array is already sorted in $O(N)$ time, while still being able to sort an unsorted array. Can you use Bubble Sort?
A: Yes! Because of the isSwapped optimization flag, if the input array is already perfectly sorted [1, 2, 3, 4], Bubble Sort runs its inner loop exactly once, swaps nothing, hits the if (!isSwapped) break; line, and instantly terminates in $O(N)$ time. This is its only theoretical advantage over standard Selection Sort (which blindly takes $O(N^2)$ even if the array is already sorted).