Selection Sort §

The core idea of selection sort is compare 2 items (e.g. A and B) and swap them if B is larger than A.

Notice anchor can be changed during comparison. as you can see, only one swapping is needed during a single iteration.

It is called selection sort because it repeatedly selects the next-smallest element and swaps it into the right place.

Solution §

Pseudo code

selectionSort(array, size)
  repeat (size - 1) times
  set the first unsorted element as the minimum
  for each of the unsorted elements
    if element < currentMinimum
      set element as new minimum
  swap minimum with first unsorted position
end selectionSort

def selectionSort(array, size):
    for step in range(size):
        min_idx = step
        for i in range(step + 1, size):
            if array[i] < array[min_idx]:
                min_idx = i
        (array[step], array[min_idx]) = (array[min_idx], array[step])
 
data = [-2, 45, 0, 11, -9]
selectionSort(data, len(data))
print(data)

var swap = function (array, firstIndex, secondIndex) {
  var temp = array[firstIndex];
  array[firstIndex] = array[secondIndex];
  array[secondIndex] = temp;
};
 
var indexOfMinimum = function (array, startIndex) {
  var minValue = array[startIndex];
  var minIndex = startIndex;
  for (var i = minIndex + 1; i < array.length; i++) {
    if (array[i] < minValue) {
      minIndex = i;
      minValue = array[i];
    }
  }
  return minIndex;
};
 
var selectionSort = function (array) {
  var index;
  for (var i = 0; i < array.length; i++) {
    index = indexOfMinimum(array, i);
    swap(array, i, index);
  }
};

Time Complexity §

The time complexity of the selection sort is the same in all cases. At every step, you have to find the minimum element and put it in the right place. The minimum element is not known until the end of the array is not reached.

Best: O(n^2) Worst: O(n^2) Average: O(n^2)

Reference §

https://www.khanacademy.org/computing/computer-science/algorithms/sorting-algorithms/a/selection-sort-pseudocode https://www.programiz.com/dsa/selection-sort