0; i < aLength-1; i++) { /* find the min element in the unsorted a[i .. aLength-1] */ /* assume the min is the first element */ int jMin = i; /* test against elements after i to find the smallest */ for (j = i+1; j < aLength; j++) { /* if this element is less, then it is the new minimum */ if (a[j] < a[jMin]) { /* found new minimum; remember its index */ jMin = j; } } if (jMin != i) { swap(a[i], a[jMin]); } } 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 elements (taking comparisons) and then swapping it into the first position. Finding the next lowest element requires scanning the remaining elements and so on. Therefore, the total number of comparisons is By arithmetic progression, which is of complexity in terms of number of comparisons. Each of these scans requires one swap for elements (the final element is already in place). Comparison to other sorting algorithms Among quadratic sorting algorithms (sorting algorithms with a simple average-case of Θ(n2)), selection sort almost always outperforms bubble sort and gnome sort. Insertion sort is very similar in that after the kth iteration, the first elements in the array are in sorted order. Insertion sort's advantage is that it only scans as many elements as it needs in order to place the st element, while selection sort must scan all remaining elements to find the st element. Simple calculation shows that insertion sort will therefore usually perform about half as many comparisons as selection sort, although it can perform just as many or far fewer depending on the order the array was in prior to sorting. It can be seen as an advantage for some real-time applications that selection sort will perform identically regardless of the order of the array, while insertion sort's running time can vary considerably. However, this is more often an advantage for insertion sort in that it runs much more efficiently if the array is already sorted or "close to sorted." While selection sort is preferable to insertion sort in terms of number of writes ( swaps versus up to swaps, with each swap being two writes), this is roughly twice the theoretical minimum achieved by cycle sort, which performs