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
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.
