Basic: Bubble, Selection, and Insertion

Introduction: The Quadratic Trio

Sorting is the "Hello World" of algorithmic complexity. While modern systems use advanced algorithms like Quicksort or Timsort (built into JavaScript's .sort()), every engineer must understand the basics first.

The three algorithms covered here—Bubble, Selection, and Insertion—share a common trait: they are all O(n^2) (Quadratic) in the average case. This means if you double the input size, the processing time quadruples. They are generally too slow for large datasets, but they teach us vital concepts about swapping, stability, and "in-place" memory management.

1. Bubble Sort: The Sinking Ship

The simplest concept to grasp, but arguably the worst performer.

The Logic:

Iterate through the array. Compare every adjacent pair. If arr[i] > arr[i+1], swap them. Repeat this process until no swaps are needed.

The largest elements "bubble" up to the end of the array with each pass.

JavaScript Implementation

function bubbleSort(arr) {
    let noSwaps;
    for (let i = arr.length; i > 0; i--) {
        noSwaps = true;
        for (let j = 0; j < i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // Swap!
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                noSwaps = false;
            }
        }
        // Optimization: If no swaps happened, it's already sorted!
        if (noSwaps) break;
    }
    return arr;
}

2. Selection Sort: The Minimalist

Selection Sort improves on Bubble Sort by minimizing the number of swaps (writing to memory).

The Logic:

Scan the entire unsorted portion of the array to find the Minimum element. Swap that minimum with the first element of the unsorted portion. Repeat.

JavaScript Implementation

function selectionSort(arr) {
    for (let i = 0; i < arr.length; i++) {
        let lowest = i;
        for (let j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[lowest]) {
                lowest = j;
            }
        }
        // Only swap if we found a new low
        if (i !== lowest) {
            let temp = arr[i];
            arr[i] = arr[lowest];
            arr[lowest] = temp;
        }
    }
    return arr;
}

3. Insertion Sort: The Professional's Choice

Of the three basic algorithms, this is the only one you might actually see in production code (as part of hybrid algorithms).

The Logic:

Builds the sorted array one item at a time, similar to how you sort playing cards in your hand. You take the next card and slide it back into the correct position in the "sorted" portion of your hand.

Why it stands out: It performs exceptionally well on nearly sorted data.

JavaScript Implementation

function insertionSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        let currentVal = arr[i];
        let j = i - 1;
        
        // Shift elements to the right to make room
        while (j >= 0 && arr[j] > currentVal) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = currentVal;
    }
    return arr;
}

Comparative Analysis

Algorithm	Best Case (Time)	Average Case (Time)	Worst Case (Time)	Space Complexity
Bubble Sort	O(n)	O(n^2)	O(n^2)	O(1)
Selection Sort	O(n^2)	O(n^2)	O(n^2)	O(1)
Insertion Sort	O(n)	O(n^2)	O(n^2)	O(1)

Expert Insight: Why Insertion Sort Lives On

You might ask: "If they are all O(n^2), why do we care?"

1. Online Algorithms: Insertion Sort is an "Online" algorithm. It can sort data as it receives it. You don't need the full array upfront.

2. Small Data Efficiency: For very small arrays (e.g., < 20 items), Insertion Sort is often faster than Merge Sort or Quick Sort because it has less overhead (no recursion stack, no complex partitioning logic).

3. Hybrid Approaches: V8 (Chrome's JS engine) and Python's Timsort actually switch to Insertion Sort when the partition size gets small enough. They use the heavy machinery for the big picture, but Insertion Sort for the fine details.

Conclusion

1. Never use Bubble Sort in production. It is purely educational.

2. Avoid Selection Sort. Even though it minimizes writes, it is slow and unstable.

3. Respect Insertion Sort. It is the "little engine that could" of sorting. It is the best choice for small or nearly-sorted datasets.