What is Selection Sort Algorithm in Data Structures? | Data Structures Tutorial

In this article, you will understand the selection sort algorithm in brief.

The selection algorithm selects the smallest element from an unsorted list in each iteration and it places the element at the beginning of the unsorted list. 

Selection Sort Algorithms

1. Set the first element value as a minimum. 
2. Do the comparison of the minimum value with the second element. If the value of the second element is greater than the value of the minimum element, then assign the second element as a minimum. The same goes for the third element, and so on. The process will go on till the last element.
3. After completing every iteration, the minimum is placed in the front of the unsorted list. 
4. In each iteration, indexing starts from the first element of the unsorted list. then repeat steps 1 to 3 until all the elements of the list are placed in the correct positions. 

Selection_sort(array, size)

  repeat(size-1) times

  set the First value of the list as a minimum

  For the unsorted list

     if element < Minimum

       Set the element as the new minimum value

  swap minimum with the First unsorted list

end Selection_sort

Complexity

Time complexity

The best case complexity is O(n2), the average case complexity is O(n2), and the worst case complexity is O(n2).

Space complexity is O(1).

Occurrence of each complexity

1. Best case complexity: It happens when the entire array is sorted.
2. Average case complexity: It happens when the elements of the array are in puzzled order.
3. Worst case complexity: It happens when we want to sort in ascending order and the array is in descending order.

Applications of Selection Sort

• It is used if a small list needs to be sorted.
• It is used if the swapping cost of the element does not make any difference.
• It is used if checking on all the elements is mandatory.
• It is used when the cost of writing to memory does matter.