Selection Sort

selection sort is an introductory level sorting scheme and its idea is straightforward: find the minimal number in each traverse of the unsorted part of list and replace it with first element on unsorted part of list to become a member of the sorted list, until the unsorted list is empty.

Pseudocode

SELECTION_SORT(array, length)
  for i := 1 to n - 1
    min := i
    for j := i + 1 to n
      if array[j] < array[min]
        min := j
      if min != i
        swap array[i] and array[min]

Note: the comparison step between index i and min value is complementary to improve the efficiency in case the element itself has to swap with itself.

Algorithm Analysis

selection sort takes (𝒩 - 1) + (𝒩 - 2) + ... + 0 ≈ 𝒩2 / 2 compares and 𝒩 exchanges.

No matter how the presortedness of inputs, the algorithm running time is quadratic. It is worth noted that selection sort scheme should not be used in most of scenarios except for cases that desire minimal cost of element exchanges. Therefore, according to asymptotic notation, selection sort worst-case running time is Ο(n2).