- December 30, 2020
Selection sort is the one of the well known sorting algorithms. This sorting algorithm is an in-place comparison-based algorithm in which the list is divided into two parts, the sorted part at the left from small to large values and the unsorted part at the right end. At first, the sorted part is empty array/list and the unsorted part is the entire list/array.
There are two indicators which represents the current item and smallest current item in the unsorted list/array. The smallest element is selected from the unsorted array and selected swapped with the left element in unsorted list, and then this item becomes the last item of the sorted array. This process continues moving unsorted array boundary by one element to the right.
This algorithm is not suitable for large data sets as its average and worst case complexities are of Ο(n2), where n is the number of items in the list/array.
Selection sort is not difficult to analyze compared to other sorting algorithms, since none of the loops depend on the data in the array. Selecting the minimum requires scanning n elements n-1 comparisons and then swapping it into the first position.
Finding the next lowest element requires scanning the remaining n-1 elements and so on. Therefore, the total number of comparisons is