Question

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

5, 2, 3, 1, 0, 2, 1, 5, 0  

Answer 1

Counting Sort Algorithm:-

Counting_Sort(arr, s)

max <- find largest element in the array.

initialize count array with all zeros

for j <- 0 to s

find the total count of each unique element and store the count at jth index in count arr

for i <- 1 to max

find the cumulative sum and store it in count array itself

for j <- s to 1

restore the elements to arr

decrease count of each element restored by 1

Code:-

#include<stdio.h>
#include<conio.h>
void Counting_Sort(int arr[], int s)
{
int output[100],c[100],max=arr[0];
for(int i=1;i<s;i++)
{
if (arr[i] > max)
{
       max = arr[i];
   }  
}
for(int i=0;i<=max;i++)
{
c[i]=0;
}
for(int i=0;i<s;i++)
{
c[arr[i]]++;
}
for(int i=1;i<=max;i++)
{
c[i]+=c[i-1];
}
for(int i=s-1;i>=0;i--)
{
output[c[arr[i]]-1]=arr[i];
c[arr[i]]--;
}
for(int i=0;i<s;i++)
{
arr[i] = output[i];
}
}

void Array(int arr[], int s)
{
for(int i=0;i<s;++i)
{
printf("%d\n",arr[i]);
}
}

int main()
{
int arr[] = {5, 2, 3, 1, 0, 2, 1, 5, 0};
int n =(sizeof(arr) / sizeof(arr[0]));
Counting_Sort(arr,n);
Array(arr,n);
}

Sample:-

Exexcution:-

Run:-