Selection Sort

Easy

Pick the smallest, place it in front

In simple words

Each round, find the smallest one left and put it next in line — like repeatedly picking the shortest kid remaining.

The idea

Scan the unsorted part for its minimum, then swap it to the front of that part. The sorted region grows by one element each pass.

←→stepspaceplay

1/20

Brute force

timeO(n²)spaceO(1)

Fewest swaps (n−1).

1// select the smallest each pass, place it at the front2for (let i = 0; i < n - 1; i++) {3  let min = i;4  for (let j = i + 1; j < n; j++)5    if (a[j] < a[min]) min = j;6  [a[i], a[min]] = [a[min], a[i]];7}

Input

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

Memory

i: —
min: —
j: —

Output

result: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: nums = [64, 25, 12, 22, 11]
Output:: [11, 12, 22, 25, 64]
Explanation:: Repeatedly pick the smallest and place it next.

Example 2

Input:: nums = [5, 1, 4, 2]
Output:: [1, 2, 4, 5]
Explanation:: Ends up 1,2,4,5.

Example 3

Input:: nums = [3, 3, 1]
Output:: [1, 3, 3]
Explanation:: Duplicates stay together.

Practice this problem:GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.