Sorting Technique - Counting Sort
- abhijitsathe
- Nov 13
- 3 min read
Q.1) How Counting Sort works?
Counting sort maintains a separate array to count occurrences of each element and stores them in another array as per their sorted position which is calculates on the basis of occurrences.
For example, if the first element is 12 and if it occurs 5 times in the unsorted collection then first 5 positions in the array will be assigned to 12....and so on.
Counting sort needs largest number (key) value in the collection to create counting array. For example, the largest number is 25 in the collection, counting array will be exactly of size 25.
Q.2) Is the counting sort a stable sorting method? Justify with example.
Yes, counting sort is a stable sorting method.
if we consider elements 23, 24, 12, 14, 12 , 15, 12.
In this collection , 12 occurs 3 times in positions 2, 4, and 6 respectively. When these elements get sorted 12 gets stored in the same sequence as it occurs.
Q.3) What is the time complexity of Counting sort?
Counting sort avoids two critical operations - comparisons and swapping (interchanges). Hence, it is faster than other sorting techniques. However, it needs process of finding largest element, storing elements in temporary array causes too many assignment operations.
Q.4) What is the space complexity of Counting sort?
Counting sort requires two arrays to store elements and one extra array to maintain count whose size depends on largest element in the collection.
Hence, space complexity of counting sort is O(2n + k), where k is the range of element (largest element).
Q.5) What can be said about efficiency of Counting Sort?
It avoids critical operations comparison and swapping, but has too many assignment operations. Identifying, largest element adds to extra operations.
It is not space efficient, as it requires two arrays to hold elements as well as one extra array to maintain occurrence count of each element.
Quick sort is stable sorting method, but not an in-place sort.
It is restricted to integer keys.
Q.6) What are the limitations of Counting sort?
Following are the limitations of Counting sort:
i) It is not an in-place sort method.
ii) It is not a space efficient method as it requires two arrays to hold elements (sorted and unsorted) as well as extra array to maintain count of occurrences of each element.
iii) It requires known data to find largest element in collection. Not suitable for small collection with wide range of elements.
iv) Even though it avoids comparison and swapping, it requires counting occurrences and assignment operations. Hence, work factor is more.
Q.7) Write a C program to implement Counting sort method.
/* Counting Sort */
#include <stdio.h>
#include <malloc.h>
#define MAXSZ 10
void counting_sort(int a[], int n)
{
int i;
int *count = NULL, *b = NULL; /* pointer for array*/
/* Find the maximum element in the collection*/
int max = a[0];
for(i=1;i<n;i++)
if (max < a[i])
max = a[i];
/* create an array count[] of size max+1 and initialize with 0*/
count = (int *) malloc (sizeof(int) * (max+1));
for(i=0;i<=max;i++)
count[i] = 0;
for(i=0;i<n;i++)
count[a[i]]++;
/* Define position for each element as per occurances */
for(i=1;i<=max;i++)
count[i] = count[i] + count[i-1];
b = (int *) malloc(sizeof(int)*n);
for(i=n-1;i>=0;i--)
{
b[count[a[i]]-1] = a[i];
count[a[i]]--;
}
/* Copying elements back from temporary */
for(i=0;i<n;i++)
a[i] = b[i];
}
void display(int a[], int n)
{
int i;
for(i=0;i<n;i++)
printf("%d ",a[i]);
printf("\n");
}
int main()
{
int a[MAXSZ];
int i,n;
printf("How many numbers? : ");
scanf("%d",&n);
printf("Enter %d numbers to sort ...\n",n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
counting_sort(a,n);
printf("Sorted numbers are ....\n");
display(a,n);
return 0;
}
Want to read more?
Subscribe to questionbankos.com to keep reading this exclusive post.