Selection Sort

Problem in simple words

Given an array, sort it by repeatedly selecting the smallest value from the unsorted suffix.

Core idea

Treat the left side as done. For each position, search the rest of the array for the smallest remaining value and lock it into place.

How the algorithm thinks

1. 1

   Search the suffix for the minimum

   COMPARE

   The sorted prefix is fixed. The inner scan only asks which remaining value should occupy the next position.

   Watch: minIndex and each suffix comparison.

2. 2

   Lock the next prefix position

   UPDATE

   After the minimum is known, swap it into the boundary so the sorted prefix grows by one.

   Watch: Boundary index and selected minimum value.

3. 3

   Leave the fixed prefix alone

   DISCARD

   Values before the boundary are already among the smallest values in sorted order, so the scan should not disturb them.

   Watch: Sorted prefix marker.

4. 4

   Finish when the suffix is exhausted

   RETURN

   Once every position has been selected, the whole array is sorted.

   Watch: Final sorted array.

Step-by-step logic

• -For each index i from 0 to n - 2, set minIndex = i.
• -Scan j from i + 1 to n - 1.
• -Update minIndex when nums[j] is smaller.
• -After the scan, swap nums[i] with nums[minIndex].
• -Continue until the suffix has one value left.

Complexity

Time O(n^2)·Space O(1)

Every pass scans the remaining suffix, producing about n^2 comparisons, while sorting happens in place with only a few index variables.

Implementation

This is the JavaScript implementation that generates the simulator timeline.

function selectionSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let minIndex = i;

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

    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }

  return arr;
}

Common mistakes