Counting Sort Algorithm Assignment Help
Counting sort assumes which each one of the n input elements is an integer within the range 1 to k, for some integer k. Whenever k = O(n), the sort runs within linear time.
Fundamental concept: determine, for every input element x, the number of elements less than x. This enables one to determine x’s position in the sorted array.
The code makes use of the following arrays:
- A[1..n] is the input array, with length[A] = n.
- B[1..n] holds the sorted output.
- C[1..k] provides temporary storage.
Example for Counting sort:
Fig : The operation of COUNTING_SORT on an input array A[1..8], where each element of A is positive integer no larger than k = 6.
- The array A and the auxiliary array C after line 4.
- The array C after line 7
- The output array B and the auxiliary array C after one, two and three iterations of the loop in line 9-11 respectively. Only the lightly shaded elements of array B have been filled in.
- The final sorted output array B.