What is Selection Sort and How to Implement it in JavaScript

Selection sort is a sorting algorithm that sorts by repeatedly finding the minimum element of the unsorted array then placing that element at the beginning. Every loop the algorithm advances the array index so the lowest element will be added next to the previous lowest element. This repeats until the entire input is sorted.

Selection sort has a time complexity of O(n^2) due to the two nested loops. This is one of the slowest sorting algorithms and has little practical use.

Step-By-Step Example

First Pass

unsorted index = 0;

(2, 9, 1, 4, 8) => (1,2, 9, 4, 8)

1 is the lowest so it is moved to the beginning of the unsorted index.

Second Pass

unsorted index = 1;

(1, 2, 9, 4, 8) => (1, 2, 9, 4, 8)

No change as the 2nd lowest element is in the correct place.

Third Pass

unsorted index = 2;

(1, 2, 9, 4, 8) => (1, 2, 4, 9, 8)

4 is the lowest so it is moved to the beginning of the unsorted index.

Forth Pass

unsorted index = 3;

(1, 2, 4, 9, 8) => (1, 2, 4, 8, 9)

8 is the lowest so it is moved to the beginning of the unsorted index.

Fifth Pass

unsorted index = 4;

(1, 2, 4, 8, 9) => (1, 2, 4, 8, 9)

Implementation

1const startingArray = [2, 9, 1, 4, 8]
2
3function selectionSort(arr) {
4  let unsortedArr = [...arr]
5  let sortedArr = []
6  let arrSize = unsortedArr.length
7  let n = 0
8
9  // loop once for every item in the starting array
10  while (n < arrSize) {
11    let minimum = unsortedArr[0]
12    let index
13
14    // loop through unsorted array and find minimum
15    for (let i = 0; i < arrSize; i++) {
16      if (unsortedArr[i] < minimum) {
17        minimum = unsortedArr[i]
18        index = i
19      }
20    }
21
22    // push minimum value to sorted array
23    sortedArr.push(minimum)
24
25    // remove minimum value from unsorted array
26    unsortedArr.splice(index, 1)
27
28    // advance the outer counter
29    n++
30  }
31
32  return sortedArr
33}
34
35selectionSort(startingArray) // [1, 2, 4, 8, 9]

Selection sort is more efficient than bubble sort in that the number of swaps will never be more than 0(n), however it shares the same time complexity as bubble sort O(n^2) so it is too slow to use for anything practical.

Cheers!

Find a mistake? Help me fix it by submitting a pull request.