Selection Sort

Sorting

avgO(n²)worstO(n²)spaceO(1)

Start with 20 unsorted values

1 / 291

Code

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

procedure selectionSort(A)  for i ← 0 to n − 2 do    min ← i    for j ← i + 1 to n − 1 do      if A[j] < A[min] then        min ← j      end if    end for    if min ≠ i then      swap A[i] and A[min]    end if  end for  return Aend procedure

Variables

n=20

Counters

comparisons: 0
swaps: 0

Size20

Distribution

Custom values2 to 150 whole numbers, each 1 to 999

seed 11

How it works

Scans the unsorted suffix for its smallest element and swaps it to the front. After pass i the first i + 1 elements are final, so it makes at most n − 1 swaps but always about n²/2 comparisons.

Complexity

Best: O(n²)
Average: O(n²)
Worst: O(n²)
Space: O(1)
Stable: No
In place: Yes

Selection Sort

How it works

Complexity

Search algorithms