Selection sort - jaredgorski.org

Selection sort

algorithms

Selection sort is an algorithm which sorts a list of items by comparing each item of the list to each other item of the list in order to find its sorted position. This is done by recursively finding the max (or min) of the original list and appending (or prepending) it to the resulting list and then removing it from the original list.

Efficiency

Selection sort is O(n^2) (exponential time/space) in Big O notation, because of the nested loop (since each item of the list requires iterating through each other item of the list in order to determine where it should be sorted to).

Implementation

Pseudocode:

result = []

for (let i = 1; i < list.length; i++) {
  min = i
  
  /* get min */
  for (j = i + 1; j < list.length) {
    if (list[j] < list[min]) {
      min = j
    }
  }
  
  result[min] = list[min]
}