Sorting fundamentals #2: Selection sort

Photo by Pawel Czerwinski on Unsplash

What is selection sort?

In selection sort we repeatedly pick the smallest, second smallest, third smallest, etc element from the array and put it in the first, second, third etc position of the array. Selection sort is an in place sorting algorithm, which means that it does not require additional storage space. Selection sort is not a stable sorting algorithm.

The good thing about selection sort is that it does less memory writes compared to other algorithms, such as merge sort, selection sort, quick sort, etc. But it is not the most optimal sorting algorithm in terms of memory writes. The most optimal sorting algorithm for memory writes is Cycle Sort.

Selection Sort performance

• Time complexity: O(n²)
• Space complexity: O(1)

Selection sort implementation

void selection_sort(int[] arr, int n) {
  for (int i = 0; i < n; i ++) {
    int min_idx = i;
    for (int j = i + 1; j < n; j++) {
      if (arr[j] < arr[min_idx]) {
        min_idx = j;
      }
    }
    int temp = arr[i];
    arr[i] = arr[min_ind];
    arr[min_ind] = temp;
  }
}

Subscribe to my Medium: https://medium.com/@exploreintellect/subscribe