easy

Implement Selection Sort

Sort an array in place using the selection sort algorithm.

1. Define the problem

Implement Selection Sort

Given an integer array nums, sort it in ascending order using the selection sort algorithm — do not use a built-in sort function. On each pass, scan the unsorted region to find its minimum value, then swap that value into the front of the unsorted region. Return the sorted array.

Constraints

  • 1 ≤ nums.length ≤ 1000
  • -104 ≤ numsi ≤ 104

Example

Inputnums = [5, 2, 4, 1, 3]
Output[1, 2, 3, 4, 5]

Explanation Each pass finds the smallest remaining value and swaps it to the front: 1, then 2, then 3, then 4, leaving 5 in place.

2. Know the words first

In plain terms

Unsorted region
The part of the array from the current position to the end that hasn't been placed in sorted order yet.
In place
Making the change directly inside the given array instead of building a new one.
3. Visualize the solution

Scan for the minimum, then swap it to the front

Scan for the minimum, then swap it to the front
Statusscanning pass 1

sortedEnd=0. Scanning indices 1-4, the minimum found is 1 at index 3.

What happens in this step

arr = [5, 2, 4, 1, 3], sortedEnd = 0, min so far = 5 (index 0)

  idx 1: 2 < 5  →  new min = 2 at index 1
  idx 2: 4 < 2  →  no
  idx 3: 1 < 2  →  new min = 1 at index 3
  idx 4: 3 < 1  →  no

The scan walks indices 1 through 4 tracking the smallest value seen; 1 at index 3 wins.
Step 1 of 6

Steps to visualize

  1. Set sortedEnd to 0 — everything from sortedEnd onward is unsorted.
  2. Scan from sortedEnd + 1 to the end of the array, tracking the index of the smallest value seen.
  3. Swap that minimum into index sortedEnd.
  4. Move sortedEnd forward by one and repeat until sortedEnd reaches the last index.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Scan for the minimum, then swap it to the front
Statusscanning pass 1

sortedEnd=0. Scanning indices 1-4, the minimum found is 1 at index 3.

What happens in this step

arr = [5, 2, 4, 1, 3], sortedEnd = 0, min so far = 5 (index 0)

  idx 1: 2 < 5  →  new min = 2 at index 1
  idx 2: 4 < 2  →  no
  idx 3: 1 < 2  →  new min = 1 at index 3
  idx 4: 3 < 1  →  no

The scan walks indices 1 through 4 tracking the smallest value seen; 1 at index 3 wins.
Step 1 of 6
5. Solution

Solution

solution.tsTypeScript
function selectionSort(nums) {
  for (let sortedEnd = 0; sortedEnd < nums.length - 1; sortedEnd++) {
    let minIndex = sortedEnd;

    for (let scan = sortedEnd + 1; scan < nums.length; scan++) {
      if (nums[scan] < nums[minIndex]) {
        minIndex = scan;
      }
    }

    if (minIndex !== sortedEnd) {
      const temp = nums[sortedEnd];
      nums[sortedEnd] = nums[minIndex];
      nums[minIndex] = temp;
    }
  }

  return nums;
}
Time
O(n^2)
Space
O(1)
6. Test cases

Test cases

InputExpectedCovers
nums = [5, 2, 4, 1, 3][1, 2, 3, 4, 5]example from the docstring
nums = [1, 2, 3, 4][1, 2, 3, 4]already sorted, no swaps needed but every pass still scans
nums = [9, 7, 5, 3, 1][1, 3, 5, 7, 9]fully reverse sorted, worst case for comparisons
nums = [3, 3, 1, 2, 3][1, 2, 3, 3, 3]repeated values mixed with distinct ones
nums = [7][7]smallest valid input, a single element
nums = [-3, 5, -1, 0, -8][-8, -3, -1, 0, 5]negative and positive values mixed together
nums = [2, 1][1, 2]boundary case, exactly two elements out of order

Keep reading