We start selection sort by scanning the entire given list to find its smallest element
and exchange it with the first element, putting the smallest element in its final
position in the sorted list. Then we scan the list, starting with the second element,
to find the smallest among the last n − 1 elements and exchange it with the second
element, putting the second smallest element in its final position. Generally, on the ith pass through the list, which we number from 0 to n − 2, the algorithm searches
for the smallest item among the last n − i elements and swaps it with Ai :
in their final positions
A0 ≤ A1 ≤ . . . ≤ Ai–1 ⏐ Ai, . . . , Amin, . . . , An–1
the last n – i elements
After n − 1 passes, the list is sorted.
Here is pseudocode of this algorithm, which, for simplicity, assumes that the
list is implemented as an array:
ALGORITHM SelectionSort(A[0..n − 1])
//Sorts a given array by selection sort
//Input: An array A[0..n − 1] of orderable elements
//Output: Array A[0..n − 1] sorted in nondecreasing order
for i ←0 to n − 2 do
min←i
for j ←i + 1 to n − 1 do
if A[j ]<A[min] min←j
swap A[i] and A[min]
