Counting sort

PROBLEM
Sort an array A. of N integers in between 1 and K.

ALGORITHM
Counting sort, or distribution counting, was invented by Harold H. Seward in 1954. Counting sort assumes that each of the N input elements is an integer in the range 1 to K. When K=O(N), the sort runs in O(N) time. This algorithm uses a temporary array.

PRACTICE
The following table compares four sorting algorithms. The A. array includes integers in the range 1 to Max=10,100,1000,40000.

 

Running time in seconds for N=10000
Algorithm Max = 100 Max = 1000 Max = 40000 Max = 99999
QUICKSORT 4.66  4.53  4.89  4.59 
HEAPSORT 10.26  10.67  11.58  11.18 
SHELLSORT  7.45   8.89  10.58  10.13 
COUNTING_SORT  1.88   1.95   7.93  31.85 

 

IMPLEMENTATION
Unit: nonrecursive internal subroutine
 
Global variables: the input array A. of an integer in the range 1 to K
 
Parameters: a positive integer N - number of elements in A., a positive integer K
 
Result: Reordering of input array such that

A.1<=A.2<=...<=A.N
 


COUNTING_SORT: procedure expose A.
parse arg N, K
C. = 0
do J = 1 to N
  Aj = A.J; C.Aj = C.Aj + 1
end
do J = 2 to K
  Jm1 = J - 1; C.J = C.J + C.Jm1
end
do J = N to 1 by -1
  Aj = A.J; CAj = C.Aj; B.CAj = A.J
  C.Aj = CAj - 1
end
do J = 1 to N; A.J = B.J; end
return

 

CONNECTIONS
Sorting Problem
     Heapsort
     Shellsort
     Quicksort
     Merging

Literature
Cormen T. H., Leiserson Ch. E., Rivest R. L. Introduction to Algorithms
The MIT Press, Cambridge, 1990
Sedgewick R., Algorithms
Addison-Wesley, Reading, Massachusetts, 1984

Acknowledgement
I changed the test from Max=10 ... 40000 to Max=100 ... 99999. Thanks for idea go to Walter Pachl.

Note
This test ran in the Windows 2000 Professional environment on the computer with 132MB RAM and processor x86Family 6 Mode 6 Stepping 5.


cover contents index main page

last modified 8th August 2001
Copyright 2000-2001 Vladimir Zabrodsky
Czech Republic.

mail