Bubble Selection Insertion — DSA

Bubble, Selection & Insertion Sort

Before merge sort and quicksort took over, three simple algorithms dominated introductory computer science: bubble sort, selection sort, and insertion sort. All three run in O(n²) average time and sort in-place — but they behave very differently in practice. Understanding their trade-offs is a prerequisite for knowing when to reach for something more sophisticated.

Note

All three algorithms are O(n²) on average, which makes them unsuitable for large datasets. However, insertion sort in particular is extremely useful for small arrays (n ≤ 20) and nearly-sorted data — and it is actually used inside production implementations of Timsort and Introsort for this reason.

Bubble Sort

Bubble sort is probably the first sorting algorithm most people learn. It works by repeatedly walking through the array and swapping adjacent elements that are out of order. After each full pass, the largest unsorted element has "bubbled up" to its final position at the end of the unsorted portion.

How it works:

Compare arr[0] with arr[1]. If arr[0] > arr[1], swap them.
Move to the next pair: compare arr[1] with arr[2]. Swap if needed.
Continue to the end of the array. After pass 1, the largest element is at index n-1.
Repeat for the remaining n-1 elements, n-2 elements, and so on.
After n-1 passes, the array is sorted.

Step-by-Step Walkthrough

Let us trace bubble sort on the array [64, 34, 25, 12, 22, 11, 90].

Initial:  [64, 34, 25, 12, 22, 11, 90]

Pass 1 (largest element 90 bubbles to end):
  Compare 64,34 → swap  → [34, 64, 25, 12, 22, 11, 90]
  Compare 64,25 → swap  → [34, 25, 64, 12, 22, 11, 90]
  Compare 64,12 → swap  → [34, 25, 12, 64, 22, 11, 90]
  Compare 64,22 → swap  → [34, 25, 12, 22, 64, 11, 90]
  Compare 64,11 → swap  → [34, 25, 12, 22, 11, 64, 90]
  Compare 64,90 → ok    → [34, 25, 12, 22, 11, 64, 90]  ← 90 is placed

Pass 2 (64 bubbles to second-to-last):
  [25, 12, 22, 11, 34, 64, 90]  ← 64 is placed

Pass 3:  [12, 22, 11, 25, 34, 64, 90]  ← 34 is placed
Pass 4:  [12, 11, 22, 25, 34, 64, 90]  ← 25 is placed
Pass 5:  [11, 12, 22, 25, 34, 64, 90]  ← 22 is placed
Pass 6:  [11, 12, 22, 25, 34, 64, 90]  ← 12 is placed (no swaps needed)

Final:   [11, 12, 22, 25, 34, 64, 90]

Bubble Sort Implementation

Bubble Sort — with early-exit optimization

function bubbleSort(arr) {
  const n = arr.length

  for (let i = 0; i < n - 1; i++) {
    // After pass i, the last i elements are already sorted
    // so we only need to go up to n - 1 - i
    let swapped = false  // optimization: detect if already sorted

    for (let j = 0; j < n - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        // Swap adjacent elements
        ;[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
        swapped = true
      }
    }

    // If no swap occurred in this pass, the array is already sorted
    if (!swapped) break
  }

  return arr
}

// Examples
console.log(bubbleSort([64, 34, 25, 12, 22, 11, 90]))
// → [11, 12, 22, 25, 34, 64, 90]

console.log(bubbleSort([1, 2, 3, 4, 5]))
// → [1, 2, 3, 4, 5]  (only 1 pass needed — best case O(n))

console.log(bubbleSort([5]))
// → [5]  (single element — 0 passes)

Tip

The `swapped` flag is a critical optimization. On an already-sorted array, the first pass detects zero swaps and exits immediately — reducing the best-case complexity from O(n²) to O(n). Always include this flag.

Bubble Sort Complexity Analysis

Worst case O(n²): Array is reverse-sorted. Every adjacent pair needs swapping every pass. Total comparisons = (n-1) + (n-2) + ... + 1 = n(n-1)/2.

Average case O(n²): Randomly ordered data still averages n²/4 comparisons.

Best case O(n): Array is already sorted. The optimized version exits after one pass with zero swaps.

Space O(1): Sorting is done in-place with a fixed number of variables.

Stable: Equal elements never swap (we only swap when arr[j] > arr[j+1], not >=), so relative order of equal elements is preserved.

Warning

Bubble sort performs many more swaps than selection sort. Swapping is more expensive than reading (especially with objects), so on large arrays bubble sort is often slower in practice than its O(n²) peers.

Selection Sort

Selection sort takes a different approach: instead of swapping repeatedly as you walk the array, find the minimum element in the unsorted portion and swap it to the front. Each pass places exactly one element in its final position and performs at most one swap.

How it works:

Find the minimum element in arr[0..n-1]. Swap it with arr[0].
Find the minimum element in arr[1..n-1]. Swap it with arr[1].
Repeat: at step i, find the minimum in arr[i..n-1] and swap with arr[i].
After n-1 passes, the array is sorted.

Step-by-Step Walkthrough

Initial:  [64, 25, 12, 22, 11]

Pass 0: Find min in [64,25,12,22,11] → 11 at index 4
        Swap arr[0] ↔ arr[4]  →  [11, 25, 12, 22, 64]   ✓ 11 placed

Pass 1: Find min in [25,12,22,64] → 12 at index 2
        Swap arr[1] ↔ arr[2]  →  [11, 12, 25, 22, 64]   ✓ 12 placed

Pass 2: Find min in [25,22,64] → 22 at index 3
        Swap arr[2] ↔ arr[3]  →  [11, 12, 22, 25, 64]   ✓ 22 placed

Pass 3: Find min in [25,64] → 25 at index 3
        No swap needed (already in position)              ✓ 25 placed

Pass 4: Only one element [64] remains                     ✓ 64 placed

Final:  [11, 12, 22, 25, 64]

Selection Sort Implementation

Selection Sort

function selectionSort(arr) {
  const n = arr.length

  for (let i = 0; i < n - 1; i++) {
    // Find the index of the minimum element in arr[i..n-1]
    let minIndex = i

    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j
      }
    }

    // Only swap if we found a smaller element
    if (minIndex !== i) {
      ;[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
    }
  }

  return arr
}

// Examples
console.log(selectionSort([64, 25, 12, 22, 11]))
// → [11, 12, 22, 25, 64]

console.log(selectionSort([3, 3, 3, 3]))
// → [3, 3, 3, 3]  (but NOT stable — see note below)

Warning

Selection sort is NOT stable. When two equal elements exist, the swap can change their relative order. For example: `[(3,A), (3,B), 1]` sorted by value gives `[1, (3,B), (3,A)]` — B moved ahead of A. If stability matters, use insertion sort instead.

Selection Sort Complexity Analysis

All cases O(n²): The inner loop always runs the same number of iterations regardless of input order — it must always scan the entire unsorted portion to guarantee it found the minimum. There is no early-exit optimization.

Total comparisons = (n-1) + (n-2) + ... + 1 = n(n-1)/2 in ALL cases.

At most O(n) swaps: This is selection sort's key advantage. Unlike bubble sort which can make O(n²) swaps, selection sort makes at most n-1 swaps — one per pass. This matters when swapping is expensive (e.g., swapping large records on disk).

Space O(1): In-place, constant extra memory.

Tip

Selection sort shines when **memory writes are expensive** — such as when sorting large structures with many fields, or writing to flash memory (which has a limited write endurance). The guaranteed O(n) swaps make it superior to bubble sort in those scenarios.

Insertion Sort

Insertion sort is the most practically useful of the three. It builds a sorted sub-array from left to right, inserting each new element into its correct position within the already-sorted portion. Think of how you sort playing cards in your hand: you pick up each card and slide it into the right place among the cards you are already holding.

How it works:

Start with the second element (index 1). The first element alone is trivially sorted.
Pick the current element (the "key"). Compare it with the elements to its left.
Shift all elements greater than the key one position to the right.
Drop the key into the gap that was created.
Move to the next element and repeat.

Step-by-Step Walkthrough

Initial:  [5, 2, 4, 6, 1, 3]
           ^
           sorted

Step 1:  key = 2  (index 1)
         5 > 2 → shift 5 right:  [5, 5, 4, 6, 1, 3]
         Insert 2 at index 0:    [2, 5, 4, 6, 1, 3]
         Sorted portion:          [2, 5]

Step 2:  key = 4  (index 2)
         5 > 4 → shift 5 right:  [2, 5, 5, 6, 1, 3]
         2 < 4 → stop
         Insert 4 at index 1:    [2, 4, 5, 6, 1, 3]
         Sorted portion:          [2, 4, 5]

Step 3:  key = 6  (index 3)
         5 < 6 → already in place
         Sorted portion:          [2, 4, 5, 6]

Step 4:  key = 1  (index 4)
         6,5,4,2 all > 1 → shift all right
         Insert 1 at index 0:    [1, 2, 4, 5, 6, 3]
         Sorted portion:          [1, 2, 4, 5, 6]

Step 5:  key = 3  (index 5)
         6,5,4 > 3 → shift right
         2 < 3 → stop
         Insert 3 at index 2:    [1, 2, 3, 4, 5, 6]

Final:   [1, 2, 3, 4, 5, 6]

Insertion Sort Implementation

Insertion Sort

function insertionSort(arr) {
  const n = arr.length

  for (let i = 1; i < n; i++) {
    const key = arr[i]  // element to be inserted
    let j = i - 1

    // Shift elements of arr[0..i-1] that are greater than key
    // one position to the right
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j]  // shift right (not a swap — faster!)
      j--
    }

    // Place key in its correct position
    arr[j + 1] = key
  }

  return arr
}

// Examples
console.log(insertionSort([5, 2, 4, 6, 1, 3]))
// → [1, 2, 3, 4, 5, 6]

// Best case: already sorted — O(n)
console.log(insertionSort([1, 2, 3, 4, 5]))
// → [1, 2, 3, 4, 5]  (inner while loop never executes)

// Nearly sorted: very fast in practice
console.log(insertionSort([1, 2, 4, 3, 5, 6]))
// → [1, 2, 3, 4, 5, 6]  (only one element out of place)

Note

Notice that insertion sort uses **shifts, not swaps**. Each shift is a single assignment (`arr[j+1] = arr[j]`), while a swap requires three assignments and a temp variable. This makes insertion sort faster than bubble sort in practice even when both are O(n²).

Binary Insertion Sort (Variant)

The standard insertion sort uses a linear scan to find the insertion position. Since the left portion is already sorted, we can use binary search to find the correct position in O(log n) — reducing the number of comparisons from O(n²) to O(n log n). However, the number of shifts remains O(n²), so the overall time complexity stays O(n²). This variant is useful when comparisons are expensive (e.g., comparing complex objects).

Binary Insertion Sort

function binaryInsertionSort(arr) {
  const n = arr.length

  for (let i = 1; i < n; i++) {
    const key = arr[i]

    // Use binary search to find insertion position in arr[0..i-1]
    let left = 0
    let right = i - 1

    while (left <= right) {
      const mid = Math.floor((left + right) / 2)
      if (arr[mid] <= key) {
        left = mid + 1  // key goes after mid
      } else {
        right = mid - 1  // key goes before mid
      }
    }

    // 'left' is now the correct insertion index
    // Shift elements right to make room
    for (let j = i; j > left; j--) {
      arr[j] = arr[j - 1]
    }

    arr[left] = key
  }

  return arr
}

console.log(binaryInsertionSort([5, 2, 4, 6, 1, 3]))
// → [1, 2, 3, 4, 5, 6]
// Comparisons: O(n log n)  |  Shifts: O(n²)  |  Overall: O(n²)

Insertion Sort Complexity Analysis

Worst case O(n²): Array is reverse-sorted. Every element must be shifted past all preceding elements. Total operations = 1 + 2 + ... + (n-1) = n(n-1)/2.

Average case O(n²): Each element is inserted about halfway into the sorted portion on average.

Best case O(n): Array is already sorted. The inner while loop never executes. Only the outer loop runs, doing one comparison per element.

Space O(1): In-place sort with a fixed number of variables.

Stable: Equal elements are never moved past each other (the while condition is arr[j] > key, not >=), so stability is preserved.

Adaptive: Performance degrades gracefully with disorder. On nearly-sorted data, insertion sort is the fastest simple sorting algorithm.

Tip

Insertion sort is used as the base case in production sorting algorithms. Python's Timsort and C++ STL's Introsort both switch to insertion sort when the sub-array size drops below a threshold (typically 16–32 elements) because the low overhead and cache friendliness outweigh the O(n²) theoretical cost at small sizes.

Side-by-Side Comparison

Property	Bubble Sort	Selection Sort	Insertion Sort
Best Time	O(n)	O(n²)	O(n)
Average Time	O(n²)	O(n²)	O(n²)
Worst Time	O(n²)	O(n²)	O(n²)
Space	O(1)	O(1)	O(1)
Stable	Yes	No	Yes
Adaptive	Yes (with flag)	No	Yes (strongly)
Swaps	O(n²) worst	O(n) always	O(n²) worst (shifts)
Comparisons	O(n²) worst	O(n²) always	O(n²) worst
Online	No	No	Yes (can sort as items arrive)

When to Use Each Algorithm

Choosing between these three algorithms is less about theoretical complexity (they are all O(n²)) and more about the specific constraints of your situation.

Use Bubble Sort When:

You need the simplest possible implementation for educational purposes
The array is very small (n < 10) and simplicity is preferred over speed
You're detecting whether an array is already sorted — the optimized version returns in O(n)
You need a stable sort and are not concerned about performance

Use Selection Sort When:

Memory writes are expensive (e.g., sorting flash memory or large disk records)
You need a guaranteed maximum of O(n) swaps, not just on average
The comparison cost is low but the swap cost is high
You need an in-place sort and the dataset is small

Use Insertion Sort When:

The array is small (n ≤ 20) — insertion sort has very low overhead
The array is nearly sorted — O(n) performance on nearly-sorted data is unmatched
You're building an online algorithm that sorts a stream as items arrive
You are implementing the base case of a hybrid sort (Timsort, Introsort)
You need a stable sort with in-place O(1) space

All Three Algorithms — Complete Test Suite

All three algorithms side by side

function bubbleSort(arr) {
  const a = [...arr]
  for (let i = 0; i < a.length - 1; i++) {
    let swapped = false
    for (let j = 0; j < a.length - 1 - i; j++) {
      if (a[j] > a[j + 1]) {
        ;[a[j], a[j + 1]] = [a[j + 1], a[j]]
        swapped = true
      }
    }
    if (!swapped) break
  }
  return a
}

function selectionSort(arr) {
  const a = [...arr]
  for (let i = 0; i < a.length - 1; i++) {
    let minIdx = i
    for (let j = i + 1; j < a.length; j++) {
      if (a[j] < a[minIdx]) minIdx = j
    }
    if (minIdx !== i) [a[i], a[minIdx]] = [a[minIdx], a[i]]
  }
  return a
}

function insertionSort(arr) {
  const a = [...arr]
  for (let i = 1; i < a.length; i++) {
    const key = a[i]
    let j = i - 1
    while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; j-- }
    a[j + 1] = key
  }
  return a
}

// Test with the same input
const test = [64, 34, 25, 12, 22, 11, 90]
console.log(bubbleSort(test))    // [11, 12, 22, 25, 34, 64, 90]
console.log(selectionSort(test)) // [11, 12, 22, 25, 34, 64, 90]
console.log(insertionSort(test)) // [11, 12, 22, 25, 34, 64, 90]

// Nearly sorted — insertion sort wins
const nearSorted = [1, 2, 3, 5, 4, 6, 7, 8]
// insertionSort does 1 shift; bubbleSort does 1 swap; selectionSort: same 28 comparisons