Notes for 13 April
COEN 251: Data Structures and Algorithms

Spring 1998

Algorithm for counting sort (from the textbook, p 176): 
COUNTING_SORT(A,B,k)
1  for i <- 1 to k
2    do C[i] <- 0
3  for j <- 1 to length[A]
4    do C[A[j]] <- C[A[j]] + 1
5  // C[i] contains the number of elements equal to i
6  for i <- 2 to k
7    do C[i] <- C[i] + C[i-1]
8  // C[i] now contains the number of elements <= to i
9  for j <- length[A] downto 1
10   do B[C[A[j]]] <- A[j]
11      C[A[j]] <- C[A[j]] -1