Content deleted Content added
No edit summary |
m →Complexity: indent math |
||
Line 113:
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 <math>n</math> elements (taking <math>n-1</math> comparisons) and then swapping it into the first position. Finding the next lowest element requires scanning the remaining <math>n-1</math> elements and so on. Therefore, the total number of comparisons is
: <math>(n-1)+(n-2)+...+1 =
\sum_{i=1}^{n-1}i</math>
By [[arithmetic progression]],
: <math>\sum_{i=1}^{n-1}i=
\frac{(n-1)+1}{2}(n-1)=
\frac{1}{2}n(n-1)=
| |||