In the selection sort, we select the minimum item.
The maximum item can also be selected in it, and both can be selected together, but the time complexity will always be n2 or more than that if we try to find solution in our method.
While sorting through it, we just have to select the item and bring it into its right position. That’s why we call it a selection sort.
- This is a simple sort because we just have to select the ‘minimum’ item but the insertion sort is much better than this because in the best-case insertion sort has the time complexity O(n) but the selection sort time will be O(n2).
- If we talk about large input, then this sort will take a lot of time because the concept of linear searching will be there.
- The time complexity of this sort is quadratic, but other sorts output in less time complexity.
- The input array is unsorted and whenever we search for the minimum item, we keep it on the left side in the unsorted array and in the left-hand side, it will become a sorted array. So sorted output array is left hand side and unsorted input array is in right hand side.
If you don’t understand, let’s look at one example.
Input is –
When n = 7
min = index 1 of Unsorted Input Array.
for i <- 1 to Max Index Unsorted Array.
if min > Array[i]
swap(min, Array[i])
- min = index 1 of Unsorted Input Array.
Suppose the minimum number is the value of index 1 right now, because we have just visited only one value and we do not know the rest of it. So, if we know only one value, then we will keep it minimum.
- for i <- 1 to Max Index Unsorted Array.
We have taken a variable i that will traverse or represent from second index to the maximum size of the array index.
- if (min > Array[i])
If any index value is smaller than the minimum value, then we  will keep the index value as the min value. If the index value is equal or greater than the variable value, this condition will become false and then we will go back to for loop and compare the next value of i.
- swap(min, Array[i])
If any index value is less than the supposed min variable value, then swap the values of min variable with index i of the array. So, minimum value is Array[i].
Program of Selection Sort in C
Â
Time Complexity of Selection Sort
Â
In best case, worst case and average case time complexity will be O(n2).
In the Best case, when we keep the value of index 1 at a minimum, then the number of operations or comparisons will be n-1.
keep index 2 minimum, then comparisons will be n-2.
keep index 3 as minimum then comparisons will be n-3.
Similarly, there are number of operations or comparisons in the entire selection sort.
= (n-1) + (n-2) + (n-3) + … + 3 + 2 + 1
= n(n-1)/2 = O(n2)
Â
In the Worst-case, the method of the best case will also follow. But in this case, we also swap.
Example – the size of the  input is  n = 7, but it  is not necessary to have a non-increasing array every time. The one in which swapping is the most, the worst case isÂ
Â
Enter the size of the array : 7
Enter the 7 item of the array : 6 11 4 15 16 1 8
Iteration 1 : 1 11 4 15 16 6 8
Iteration 2 : 1 4 11 15 16 6 8
Iteration 3 : 1 4 6 15 16 11 8
Iteration 4 : 1 4 6 8 16 11 15
Iteration 5 : 1 4 6 8 11 16 15
Iteration 6 : 1 4 6 8 11 15 16
Time complexity
= n2 for comparison + (n-1) for swapping
= O(n2)
The same time complexity will remain in the average case. The number of comparisons will be n2 and swapping can go from 1 to n-1.
Â
Space Complexity of Selection Sort
The space complexity is O(1) because in the code, we have used only 2 variables for swapping.
Test Yourself
Q1- Explain the concept of Selection Sort and how it works.
Selection Sort is a simple comparison-based sorting algorithm that works by repeatedly selecting the minimum element from the unsorted part of the array and placing it at the beginning. It divides the input array into two parts: the sorted part on the left and the unsorted part on the right. In each iteration, it finds the minimum element in the unsorted part and swaps it with the first element in the unsorted part.
Q2- Why is Selection Sort considered inefficient for large input arrays?
Selection Sort uses linear searching to find the minimum element in the unsorted part of the array in each iteration. This linear search makes it inefficient for large input arrays, leading to a time complexity of O(n^2). As the size of the input array increases, the number of comparisons and swaps also increases significantly.
Q3- Why is Selection Sort called Selection Sort?
Selection Sort is called so because it repeatedly selects the minimum element from the unsorted part of the array and places it at the beginning. It “selects” the minimum element and “sorts” the input array by placing the selected elements in their correct positions.
Q4- What is the main advantage of Selection Sort over Bubble Sort?
The main advantage of Selection Sort over Bubble Sort is that it minimizes the number of swaps required to sort the array. Bubble Sort may require many swaps to move the largest elements to their correct positions, while Selection Sort directly selects the minimum element and swaps it to the appropriate place.
Q5- How does Selection Sort handle duplicate elements in the input array?
Selection Sort does not distinguish between duplicate elements during the sorting process. As a result, it does not preserve the original order of equal elements in the sorted output. This property makes Selection Sort an unstable sorting algorithm.
Q6- Can Selection Sort be optimized to improve its efficiency further?
While Selection Sort’s basic concept remains unchanged, certain optimizations can be applied to reduce the number of unnecessary comparisons and swaps. For example, in the inner loop, we can find both the minimum and maximum elements simultaneously to reduce the number of iterations.
Q7- What is the time complexity of Selection Sort in the best-case scenario?
O(1)
O(log n)
O(n)
O(n^2)
Ans – (4)
Explanation: In the best-case scenario, Selection Sort still requires multiple passes through the array, resulting in a time complexity of O(n^2).
Q8- How many passes does Selection Sort make through the array in the worst-case scenario?
n passes
log n passes
n/2 passes
n-1 passes
Ans – (4)
Explanation – In the average-case scenario, Selection Sort makes n-1 passes through the array, where n is the size of the input array.
