Selection Sort

Selection Sort

Selection sort takes a different approach from bubble sort. Instead of comparing neighbors, it finds the smallest element in the unsorted portion and swaps it into its correct position. Think of it like arranging books on a shelf — you scan the pile, find the shortest book, and put it first.

The name makes sense: each iteration, you select the minimum element. It's straightforward and predictable, which has its own charm. The number of swaps is always O(n), which can be an advantage when writes are expensive.

Step-by-Step Visualization

Let's sort [64, 25, 12, 22, 11]. Pass 1: find minimum (11 at index 4), swap with index 0 → [11, 25, 12, 22, 64]. Pass 2: find minimum in remaining (12 at index 2), swap with index 1 → [11, 12, 25, 22, 64]. Pass 3: find minimum (22 at index 3), swap with index 2 → [11, 12, 22, 25, 64]. Done!

See the pattern? After each pass, the sorted portion grows by one element. The key insight is that you only need one swap per pass, regardless of how scrambled the data is. That's O(n) swaps total — much fewer than bubble sort's O(n²) swaps.

function selectionSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    let minIdx = i;
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIdx]) {
        minIdx = j;
      }
    }
    if (minIdx !== i) {
      [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
    }
  }
  return arr;
}
console.log(selectionSort([64, 25, 12, 22, 11]));

Time Complexity

Selection sort is always O(n²) — no matter what. The inner loop always scans the entire remaining unsorted portion, even if the array is already sorted. That's both its weakness and its predictability. You always know exactly how long it will take.

Space complexity is O(1) since it sorts in place. The trade-off is minimal writes (n-1 swaps) but maximum comparisons. Bubble sort, by contrast, does more swaps but can terminate early.

Selection Sort vs Bubble Sort

So which is better? It depends on what you're optimizing for. Selection sort wins on the number of swaps — it does at most n-1, while bubble sort can do O(n²). If writing to memory is expensive (like flashing EEPROM), selection sort is the better choice.

Bubble sort wins when the data is nearly sorted, because it can terminate early. Selection sort doesn't have that luxury. Both are O(n²), so for real performance, you'd reach for merge sort or quick sort instead. But selection sort's simplicity makes it easy to implement and reason about.