Question

1. Sort the given keys using Counting sort algorithm. Also write the algorithm.

         4, 1, 0, 2, 1, 5, 0, 4                                                                    

No code or programs, please. Manually solve the problem, please. Thanks

Answer 1

Input data (A[]) : 4, 1, 0, 2, 1, 5, 0, 4

Since maximum value is 5, we can take count array of length 5. However to be more general, let us take a count array of lenhth 10.

Step 1: Initialize count array with 0 values.

for(i=0; i<10; i++)

count[i] = 0;

Step 2: Store the count of each element in the count array.

for(i=0; i<n; i++)

count[A[i]]++;

Thus contents of count array = [2, 2, 1, 0, 2, 1, 0, 0, 0, 0]

Step 3: Modify the count array such that each element at each index stores the sum of previous counts.

for (int i = 1; i < 10; ++i)

count[i] += count[i - 1];

Thus contents of count array = [ 2, 4, 5, 5, 7, 8, 8, 8, 8 8]

Step 4: Output each item from the input sequence in current count index followed by decreasing its count by 1.

for(i=0; i<n; i++){

output[count[A[i]]-1] = A[i];

count[A[i]]--;

Thus output[6] = 4, output[3] = 1, output[1] = 0, output[4] = 2, output[2] = 1, output[7] = 5, output[0] = 0, output[5] = 4

Step 5: Copy output to original array.

for(i=0;i<n;i++)

A[i] = output[i];

Thus content of A = [0, 0, 1, 1, 2, 4, 4 5]