Selection Sort in Pseudocode

SelectionSort(A)
// GOAL: place the elements of A in ascending order
1  n := length[A]
2  for i := 1 to n
3     // GOAL: place the correct number in A[i]
4     j := FindIndexOfSmallest( A, i, n )
5     swap A[i] with A[j]
      // L.I. A[1..i] the i smallest numbers sorted
6  end-for
7  end-procedure


FindIndexOfSmallest( A, i, n )
// GOAL: return j in the range [i,n] such 
//       that A[j]<=A[k] for all k in range [i,n]
1  smallestAt := i ;
2  for j := (i+1) to n
3     if ( A[j] < A[smallestAt] ) smallestAt := j
      // L.I. A[smallestAt] smallest among A[i..j]
4  end-for
5  return smallestAt
6  end-procedure

Counting code

In FindIndexOfSmallest, dominated by line 3, run n-i times.

In SelectionSort, dominated by line 4, run n times, the i-th call to FindIndexOfSmallest taking time n-i, i=1, ..., n.

Burton Rosenberg
Creation Date: Wed Aug 25 14:48:27 EDT 2004