Selection sort is one of the basic sorting algorithms which is easy to understand and implement. The idea is simple: given an array of elements to be sorted,
- Divide the array into two subarrays: sorted and unsorted subarrays
- In each iteration, find the maximum/minimum element in the unsorted subarray and swap it with the first element of the unsorted subarray. After swapping, the first element of the unsorted subarray will be appended to the sorted subarray. Swapping the minimum value will sort the elements in ascending order while swapping the maximum value will sort the elements in descending order.
- Continue the iteration until the last element
Let’s look at an example for better understanding.
Suppose the array of numbers to be sorted in ascending order is (8,4,6,3,1,9,5)
Initially, the entire array will be the unsorted subarray as shown in the figure above. We find the minimum value 1 and swap it with 8, which is the first element of the unsorted subarray. The sorted subarray is colored in yellow. The next minimum value in the unsorted subarray is 3. We swap it with 4 which is the first element of the unsorted subarray. Thus, in the iᵗʰ iteration, we swap the minimum value with the iᵗʰ element of the array. After m number of iterations, the first m elements of the array will be in sorted order.
Implementation in C
Analysis of Selection Sort
- Selection sort is an in-place algorithm which means it does not require additional memory space to perform sorting.
- The time complexity is O(n²). Suppose the number of elements to be sorted is n, initially, the minimum value should be found among n elements which requires (n-1) comparisons. In the next iteration, it requires (n-2) comparisons. The following figure shows the number of comparisons required in each iteration.
Hence, the total number of comparisons required would be (n-1) + (n-2) + ….. + 2 + 1 which can be simplified as n(n-1)/2 → O(n²)
Since its time complexity is quadratic, selection sort would be very inefficient when a large number of elements has to be sorted. However, since its space complexity is O(1), selection sort can be useful when the amount of memory available is very limited.
Hope you enjoyed the article!