Counting Sort

By | May 24, 2014

Counting Sort is not a comparison sort.Counting sort assumes that each of the input element is an integer in the range 0 to k, for some integer k. When k=O(n), the sort runs in O(n) time. The basic idea of counting sort is to determine, for each input element x, the number of elements less than x. This information can be used to place element x directly into its position in the output array. For example, if there are 10 elements less than x, then x belongs in output position 11. This scheme must be modified slightly to handle the situation in which several elements have the same value, since we don’t want to put them all in the same position.

In the code for counting sort, we assume that the input is an array A[], and thus length[A] =n. We require two other arrays: the array B[] holds the sorted output, and the array C[] provides temporary working storage.

Below is the C++ code for counting sort algorithm.

For more tutorials see our tutorials page

Leave a Reply

Your email address will not be published. Required fields are marked *