As you know sorting is a technique by which we can arrange elements either in ascending order or descending order. We have a lot of sorting techniques like Selection, Bubble, Insertion, Quick, Radix etc. In this article, we discuss about Selection Sort.
Selection Sort
- Selection sort is a sorting algorithm that selects the smallest element from an unsorted list in each iteration and places that element at the beginning of the unsorted list.
- As the name suggests, we also call it in-place comparison-based algorithm where we select a place (position) and compare that element with other elements.
Time Complexity
- Worst Case Complexity : O (n2) : If we want to sort in ascending order and the array is in descending order then, the worst case occurs.
- Best Case Complexity : O (n2) : It occurs when the array is already sorted.
- Average Case Complexity : O (n2) : It occurs when the elements of an array are in mixed order, i.e. some elements are in sorted form and other are in unsorted form.
- The time complexity of the selection sort is the same in all cases. At every step, we 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.
Working of Selection Sort :
Suppose we have an array of integer, like :
Selection Sort
In the above array, select the first position (i=0) and compare that element (45) with the second element (32). If the second element is smaller then swap it with first element. Like :
Selection Sort Iteration 1
After swapping, again the first position element (32) is compared with third element (57), if the third element is smaller then swap it with first element otherwise nothing is done. Like in this case, if we compare 32 with 57, then nothing will happen.
Now compare the first position element (32) with fourth element (25), if the third element is smaller then swap it with first element otherwise nothing is done. In this case, as 25 is smaller than 32 then swapping will take place.
Again compare the first position element (25) with fifth element (12), if the third element is smaller then swap it with first element otherwise do nothing. In this case, as 12 is smaller than 25 then swapping will take place.
And finally at the last of first iteration, we will find smallest element on the top of the list. The same process is applied to the rest of the items in the array, like :
Selection Sort Iteration 2
Selection Sort Iteration 3
Selection Sort Iteration 4
Advantages of Selection Sort
- On small lists, it performs incredibly well.
- When applied to previously sorted objects, it works wonderfully i.e. performance is too good.
- Because it is an in-place sorting algorithm, no additional temporary storage is required beyond what is needed to hold the original list.
Disadvantage of Selection Sort
- The primary disadvantage of the selection sort is its poor efficiency when dealing with a huge list of items.
- The number of iterations made during the sorting is n-squared, where n is the total number of elements in the list.
- Other sorting techniques, such as quicksort, have better performance compared to the selection sort.
Algorithm of Selection Sort
Selection Sort Algorithm
In the above algorithm, “a” is a linear array of size “n”. This sub-algorithm finds the location “loc” of the smallest element among a[k-1],a[k+1],a[k+2] and so on. Temporary variable “small” is used to hold the current smallest element and variable “j” is used as loop control variable.
Program of Selection Sort in C-Language
Selection Sort Program
Now I hope from the above content you have a basic understanding of Selection sort and how it work.
