In computer science, selection sort is an in-place comparison sorting algorithm. It has a O(n2) time complexity, which makes it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity and has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited. The algorithm divides the input list into two parts: a sorted sublist of items which is built up from left to right at the front (left) of the list and a sublist of the remaining unsorted items that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right. The time efficiency of selection sort is quadratic, so there are a number of sorting techniques which have better time complexity than selection sort.
Example Here is an example of this sort algorithm sorting five elements:
(Nothing appears changed on these last two lines because the last two numbers were already in order.) Selection sort can also be used on list structures that make add and remove efficient, such as a linked list. In this case it is more common to remove the minimum element from the remainder of the list, and then insert it at the end of the values sorted so far. For example:
arr[] = 64 25 12 22 11
// Find the minimum element in arr[0...4] // and place it at beginning <11> 25 12 22 64
// Find the minimum element in arr[1...4] // and place it at beginning of arr[1...4] 11 <12> 25 22 64
// Find the minimum element in arr[2...4] // and place it at beginning of arr[2...4] 11 12 <22> 25 64
// Find the minimum element in arr[3...4] // and place it at beginning of arr[3...4] 11 12 22 <25> 64
Implementations Below is an implementation in C.
Complexity 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 {\displaystyle n} elements (taking n − 1 {\displaystyle n-1} comparisons) and then swapping it into the first position. Finding the next lowest element requires scanning the remaining n − 1 {\displaystyle n-1} elements (taking n − 2 {\displaystyle n-2} comparisons) and so on. Therefore, the total number of comparisons is
( n − 1 ) + ( n − 2 ) + ⋯ + 1 = ∑ i = 1 n − 1 i {\displaystyle (n-1)+(n-2)+\dots +1=\sum _{i=1}^{n-1}i}
By arithmetic progression,
∑ i = 1 n − 1 i = ( n − 1 ) + 1 2 ( n − 1 ) = 1 2 n ( n − 1 ) = 1 2 ( n 2 − n ) {\displaystyle \sum _{i=1}^{n-1}i={\frac {(n-1)+1}{2}}(n-1)={\frac {1}{2}}n(n-1)={\frac {1}{2}}(n^{2}-n)}
which is of complexity O ( n 2 ) {\displaystyle O(n^{2})} in terms of number of comparisons.
… excerpt ends here. Continue reading the full article.
