The Interview Question Today#21(16-3-19)

Question:

Comparison Counting Sort

Solution:

 Approach:

1. First of all, I am reading n elements in the array a[]. While reading the array elements I have also calculated the maximum element.

2. Now the actual sorting is done in the counting_sort() function. Here I am counting the occurrence of each element in the array a[] and then storing it at the index equal to the value of that element. For example, the occurrence of element 5 will be stored at index 5, the occurrence of element 9 will be stored at index 9 and so on.

3. As the value at each index in the count[] array is the occurrence of that index or element, so the elements are printed in ascending order by printing each index number of times equal to its corresponding value.

 ALGORITHM ComparisonCountingSort(A[0..n - 1])

//Sorts an array by comparison counting

//Input: ArrayA[0..n - 1] of orderable values

//Output: ArrayS[0..n - 1] of A’s elements sorted in nondecreasing order

for i ← 0 to n - 1 do

Count[i] ← 0

for i ← 0 to n - 2 do

forj ← i + 1 to n - 1 do

ifA[i] < A[j]

Count[j] ← Count[j] + 1

else Count[i] ← Count[i] + 1

for i ← 0 to n - 1 do

S[Count[i]] ← A[i]

return S

C Program:

/*  C Program for counting sort */

#include <stdio.h> /*  Counting sort function  */

void counting_sort(int A[], int k, int n)

{

    int i, j;

    int B[15], C[100];

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

        C[i] = 0;

    for (j = 1; j <= n; j++)

        C[A[j]] = C[A[j]] + 1;

    for (i = 1; i <= k; i++)

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

    for (j = n; j >= 1; j--)

    {

        B[C[A[j]]] = A[j];

        C[A[j]] = C[A[j]] - 1;

    }

    printf("The Sorted array is : ");

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

        printf("%d ", B[i]);

}

/*  End of counting_sort()  */ /*  The main() begins  */

int main()

{

    int n, k = 0, A[15], i;

    printf("Enter the number of input : ");

    scanf("%d", &n);

    printf("\nEnter the elements to be sorted :\n");

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

    {

        scanf("%d", &A[i]);

        if(A[i]>100){//max element should 100

            printf("error max element should <=100");

            exit(0);

        }

        if (A[i] > k) {

            k = A[i];

        }

    }

    counting_sort(A, k, n);

    printf("\n");

    return 0;

}

Output:

Enter the number of input : 5 Enter the elements to be sorted :

3

2

7

9

1

The Sorted array is : 1 2 3 7 9