Counting Sort

no comparisons

Assume n elements in range 1 to k. When k = O (n), running time is O (n).

Arrays:

A[1 ... n]    original unsorted array

B[1 ... n]    array to hold sorted output

C[1 ... k]    working array to hold counts

Counting-Sort ( A, B, k )

  1. for i 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] now contains the number of elements equal to k.

  6. for i ¬ 2 to k

  7.      do C[i] ¬ C[i] + C[i-1]

  8. // C[i] now contains the number of elements less than or equal 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

Each line below shows the step by step operation of counting sort.

A 3 6 4 1 3 4 1 4 C 2 0 2 3 0 1

 

 C 2 2 4 7 7 8

 

B             4   C 2 2 4 6 7 8

 

B   1         4   C 1 2 4 6 7 8

 

B   1       4 4   C 2 2 4 5 7 8

 

B  1 1  3 3 3 4 4  6

Cost of Counting Sort:

  1. O (k)
  2. O (n)
  3. O (k)
  4. O (n)

O ( n + k ) if k = O (n) = O (2 n) = O (n)

  • In place: No
  • Divide and conquer? No
  • Stable: Yes (Numbers with equal values in A[] appear is same order in B[].)

Why is its cost better than W ( n lg n)? NO COMPARISONS!

 

 
Sorting in Linear Time - 2 of 4