Similar to the bubble sort and insertion sort algorithms, the selection sort algorithm is a comparison-based sorting algorithm. The selection sort algorithm divides the array or list into two portions: the sorted portion and the unsorted portion. Assuming that the selection sort algorithm will be used to sort the elements in ascending order, it repeatedly looks for the smallest element in the unsorted portion and then places it at the leftmost position, swapping it with the first element. If the algorithm is used to sort elements in descending order, then the algorithm will look for the largest element. The same process will happen in both situations.
Referring to the picture below, the selection sort algorithm is applied.
So, in the example above, an array of [7,5,4,2] is meant to be sorted in ascending order through the selection sort algorithm. Initially, the unsorted portion is considered as the original array. This was not seen in the picture but is still implied. Based on the picture above, the first step is to divide the array into a sorted and unsorted array by getting the smallest element in the unsorted portion and placing it in the sorted portion. In this case, 2 is the smallest element in the unsorted array. This will swap with the current first element in the array 7. This will result in an array of [2,5,4,7]. The leftmost portion is the first element to be inserted in the sorted portion. This step will be repeated until there are no elements in the unsorted portion. Therefore, after the first step, the sorted portion of the array is [2], while the unsorted portion is [5,4,7].
To continue on the second step, the smallest element in the unsorted portion is 4. 4 will then be swapped with the current first element in the unsorted portion, which is 5. This will result in the unsorted array of [4,5,7]. After this, 4 will be moved to the sorted portion. Therefore, the sorted portion has [2,4], while the unsorted has [5,7]. Continuing on the third step, the smallest element is 5 in the unsorted array. As it is already placed in the leftmost portion, it is not necessary for it to be swapped. 5 is then moved to the sorted array portion. Resulting in the sorted portion of [2,4,5] and the unsorted portion of [7]. With one element remaining in the unsorted portion, it is already the largest element in the array. This largest element, in this case, is 7, which will now be moved to the sorted array. The final sorted array is now [2,4,5,7].
The selection algorithm has the same time complexity as bubble sort and insertion algorithms. It is of n squared or n raised to 2, where n is the number of elements in the array. This is due to the finding of minimum or maximum elements in the unsorted portion, depending on the type of sorting, whether ascending or descending, in every iteration. The selection sort algorithm is also not efficient in handling large datasets but is simpler than more complex sorting algorithms.
The selection sort has its use cases. This includes:
Teaching basic sorting concepts for educational purposes
It can be used in sorting small arrays and lists where code simplicity is more important.
It can also be used if other sorting algorithms can not be used because of resource constraints.
Overall, the concept of the selection sort algorithm is easy to grasp as it prioritizes the minimum or maximum element depending on the sorting order and then places it in the sorted portion. Although it is still not efficient in handling large datasets, it can be used for educational purposes where simplicity is valued more than efficiency.
Posted using Honouree