Selection Sort Algorithm

Selection sort is an algorithm used to sort (or order) elements present in a list. It sorts elements present in the list by iterating over the list/array several times and selects and places nth smallest element at the correct position. So in the first pass or iteration through the list, the algorithm selects the first smallest element and places it in the first position. In the second pass or iteration, the algorithm selects the second smallest element and places it in the second position and so on.

For example, if we have a list of items from different months like: [dec, feb, mar, jan, aug], in the first iteration we select the first least element and place it in the first position. The first least element is jan, so we place it at the first position: [jan, dec, feb, mar, aug]. Now we look for the second least element (feb) and place it in the second position: [jan, feb, dec, mar, aug]. Similarly we select and place the third, fourth and fifth least elements at the correct positions and the list will be sorted: [jan, feb, mar, aug, dec]. Visualizations provided below makes it clear on how this process can be done in place.

If sorting is to be done in descending order, the algorithm finds and places the nth largest element in the nth iteration at nth position instead of placing the nth smallest element at nth position.

Idea Behind the Algorithm

Think of the entire input list as two portions: unsorted portion of list towards left and the sorted portion of list towards right. Initially the entire array is unsorted and so the size of sorted portion is zero. We slowly increase the sorted portion of array from left side by selecting the nth smallest element and by adding it at the end of sorted array (at nth position).

For example, let’s say the selection sort algorithm is given the below array as the input:

The entire array shown above is unsorted. So the size of sorted portion of array is 0 and the unsorted portion size is 5 (From 0th position to 4th position).

First Iteration

The algorithm tries to select the element that should be at first position in the sorted array. Since we are trying to sort the array in descending order, the first element will be the least element present in the entire array. So the algorithm visits each element, marks the least element seen so far and finally moves the least element to the first position.

After this iteration, the sorted portion of list towards left (marked in green) increased by 1 and the unsorted portion of list decrease by 1.

Second Iteration

In this iteration, the algorithm tries to select the element that should be at second position in the sorted array. We are trying to sort the array in descending order. So in second position, the second smallest element should be present in the sorted array. Because we already picked the first smallest element and placed it at the first position, we just need to select the smallest element in the unsorted portion of array (index 1 to 4) and place it in second position.

After this iteration, the sorted portion of list towards left (marked in green) increased by 1 and the unsorted portion of list decrease by 1.

Third Iteration

In this iteration, the algorithm selects the third smallest element in the list and places it at third position. Again, since the first and second elements are already placed in first and second positions, the algorithm just keeps track of the smallest element in the unsorted portion of list and places it in third position.

After this iteration, the sorted portion of list towards left (marked in green) increased by 1 and the unsorted portion of list decrease by 1.

Fourth Iteration

Similar to the previous iterations, the algorithm selects the fourth smallest element and places it at position 4.

Fifth Iteration

The algorithm has already placed the first four elements in sorted order at correct positions. So the fifth and last element has to be in the correct position as well and so the array is sorted.

These iterations are repeated n number of times, where n is the size of input list. In the above case, the size of list is 5 and so 5 iterations are made to completely sort the list. (The last iteration is not really necessary)

Visualization of Selection Sort Algorithm

In each iteration visit all elements in the unsorted portion of array one by one and mark the smallest element observed so far. After finding the smallest element, we move to to the beginning of unsorted portion of array and mark it as sorted. We keep making iterations until all the elements are sorted.

Implementing Selection Sort Algorithm

# Selection sort algorithm written in Python language

# Function that implements selection sort algorithm
def selectionSort(array, size):
   
  # Iterate through each element in the input array
  for idx in range(size):
    min_idx = idx

    # Look for the smallest element in unsorted portion of array
    for i in range(idx + 1, size):
     
      # select the minimum element in each loop
      # (or maximum according to your requirement)
      if array[i] < array[min_idx]:
          min_idx = i
     
    # move the least element present at min_idx
    # to the beginning of unsorted portion of array at idx
    (array[idx], array[min_idx]) = (array[min_idx], array[idx])



# Let's now use the algorithm to sort an array
arr = [68, 70, 28, 94, 67, 48]
size = len(arr)
selectionSort(arr, size)
print('Sorted Array in Ascending Order:')
print(arr)

// C++ program for implementation of selection sort algorithm

#include <bits/stdc++.h>

// Function that implements selection sort algorithm
void selectionSort(std::vector<int> &arr) {
  for (int idx = 0; idx < arr.size(); idx++) {
    int min_idx = idx;
    
    // Iterate through all elements in unsorted portion of array.
    for (int i = idx + 1; i < arr.size(); i++) {

      // Select the minimum element among all elements visited so far
      if (arr[i] < arr[min_idx])
        min_idx = i;
    }

    // Put the least element observed so far at the correct position
    std::swap(arr[min_idx], arr[idx]);
  }
}

// Let us now sort an array using selection sort algorithm
int main() {
  std::vector<int> arr = {68, 70, 28, 94, 67, 48};
  selectionSort(arr);
  std::cout << "Sorted array in Acsending Order:\n";
  for(auto n : arr) std::cout << n << " ";
}

Characteristics of Selection Sort Algorithm

Time Complexity

If there is an array with 5 elements, after the first iteration, we will be sure that the first smallest element is at correct position, after the second iteration, we will be sure that the second smallest element is at correct position. And so on. So for an array of n elements, the selection sort algorithm need to make n iterations to sort the entire list. And for each iteration, it visits all the elements in the unsorted portion of list. So the time complexity of selection sort algorithm is (number of iterations) * (complexity of each iteration) = n * O(n) = O(n^2).

We do not have any checks to stop iterating further if the list is already sorted way before doing the nth iteration. So both the best and worst case time complexities remain O(n^2).

Space Complexity

Both the best and worst case space complexity of this algorithm is O(1) since we are not allocating any new list and sorting the list in place.

Stability

Any sorting algorithm is said to be stable if the relative order of elements with similar id is maintained. For example, if we are given an unordered list of objects [1#, 2%, 1%, 2#], the output has to be [1#, 1%, 2%, 2#]. i.e., the relative order of similar elements has to be maintained.

In this algorithm, if we encounter elements 2% and 2# in that order, we first place 2% and then place 2#. So the relative order of similar elements is maintained. Hence selection sort is a kind of stable sorting algorithm.

Resources & References

• Wikipedia