In computer science, “Selection Sort” is a type of comparison sort algorithm, where we compare two values of an array and swap their orders based on the comparison outcome.

Explanation:

Let’s assume we have an array ‘A’; it contains ‘n’ number of elements (i.e. A[0…n]).

The first step of the algorithm is to scan through the whole array (i.e. A[0…n]) and find the smallest value. After the entire array is scanned; swap the smallest found value with the first element (A[0]) of the array.

Now, scan the array from the second element to the last one (i.e. A[1…n]), and find the second smallest value, and swap it with the second element (A[1]) of the array.

Keep repeating the process until the entire array is sorted.

Implementation:

  • Go
  • Python
  • C

The output of the program above,

Complexity Analysis:

  • Time Complexity

    Best-case: Ω(n²)

    Average-case: θ(n²)

    Worst-case: Ο(n²)

  • Space Complexity

    Worst-case: Ο(1) ( which is excellent! )

Conclusion:

The selection sort is a very simple algorithm and requires very less amount of auxiliary memory to perform a sorting operation. On the other hand, it is very inefficient for a large list and worse than the similar insertion sort. Although there are many variants of this algorithm, which improves the performance of sorting dramatically, such as Heapsort, Cocktail Sort/Double Selection Sort.