Bubble / Insertion / Selection

// ===== Pseudo-code =====
// For each pass through the array:
//   For each adjacent pair (i, i+1):
//     If a[i] > a[i+1], swap them
// Repeat until no swaps happen in a pass.

function bubbleSort(arr) {
  const a = [...arr];
  let n = a.length;
  let swapped;
  do {
    swapped = false;
    for (let i = 0; i < n - 1; i++) {
      if (a[i] > a[i + 1]) {
        [a[i], a[i + 1]] = [a[i + 1], a[i]];
        swapped = true;
      }
    }
    n--;  // largest element is at the end now
  } while (swapped);
  return a;
}

console.log(bubbleSort([5, 2, 9, 1, 7]));  // [1, 2, 5, 7, 9]

// ===== Complexity =====
// Time:
//   Best  O(n)        already sorted; one pass with no swaps
//   Avg   O(n^2)
//   Worst O(n^2)      reverse sorted
// Space: O(1) extra (in place)
// Stable: YES (equal elements keep order)

// ===== Why we don't use it =====
// O(n^2) makes it unusable at scale.
// Even on n=10_000 it does ~50 million comparisons.

// ===== Variants =====
// Cocktail sort: alternates direction each pass (slightly better)
// Comb sort: skips by a 'gap' shrunk over passes (much better in practice)
// Optimized bubble: shrink the inner-loop bound each pass

// ===== When it is OK =====
// - Teaching / interview warmup
// - Tiny arrays (< 30 items) where overhead beats fancy algorithms
// - Specific 'few wrong' near-sorted data (still O(n) best case)

// ===== Comparison with neighbours =====
// Insertion sort: O(n^2) worst, but ~2x faster than bubble in practice + better best case
// Selection sort: O(n^2), unstable, fewer swaps but more comparisons
// Quick / merge / heap: O(n log n) — what you actually use

// ===== Better real-world options =====
// JS: Array.prototype.sort() uses TimSort (O(n log n)) — used in V8, Python, Java.
// C: qsort uses introsort variant.
// Rust: Vec::sort uses TimSort-derived.

// Use the built-in sort unless writing the algorithm is the assignment.

// ===== Patterns to internalise =====
// - Bubble sort is a teaching algorithm, not a production tool
// - Recognise stable vs unstable sorts (bubble + merge + Tim ARE stable)
// - Best-case detection (no swaps in a pass = sorted)
// - Switch to insertion sort for n < 30 if you must roll your own

// ===== Pitfalls =====
// - Using bubble sort in production code
// - Forgetting the early-exit when no swap occurs
// - Off-by-one on the inner loop bound (i < n - 1)
// - Treating sort comparator as ordered when it must be transitive + total

// Useful only for tiny inputs. Insertion sort wins for small N + nearly sorted.
function bubbleSort(a) {
    for (let i = a.length - 1; i > 0; i--)
        for (let j = 0; j < i; j++)
            if (a[j] > a[j+1]) [a[j], a[j+1]] = [a[j+1], a[j]];
    return a;
}