Counting Sort in C
Here you will know about Counting Sort and get the program code of Counting Sort in C programming.
What is Counting Sort
Counting sort is an efficient sorting algorithm that works by counting the number of objects in an array that has a particular key value. Then it uses this value to sort the array. It is a non-comparative sorting algorithm, means it does not compare elements to one another to determine their order.
This makes it more efficient than other sorting algorithms such as bubble sort or insertion sort. Counting sort is often used to sort large datasets because of its speed and low memory usage.
Counting Sort time complexity
Counting Sort’s time complexity is O(n + k), where n is the number of elements, and k is the range of values. It’s efficient when k is small compared to n. It counts the occurrences of each value, then arranges them in sorted order.
The dominant factor is the sum of n and k, making it faster than comparison-based sorts for small value ranges.
Counting Sort in C Program
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | //Counting Sort in C #include<stdio.h> #include<conio.h> int main() { int a[20],b[20],c[100],n,i,k,big; //clrscr(); printf("\n***** Counting Sort in C *****\n\n"); printf("\n Enter Number of elements : "); scanf("%d",&n); printf("\n Enter value of elements : "); for(i=1;i<=n;i++) scanf("%d",&a[i]); big=a[1]; for(i=2;i<n;i++) { if(big<a[i]) big=a[i]; } for(i=0;i<=big;i++) c[i]=0; for(k=1;k<=n;k++) c[a[k]]=c[a[k]]+1; for(i=1;i<=big;i++) c[i]=c[i]+c[i-1]; for(k=n;k>=1;k--) { b[c[a[k]]]=a[k]; c[a[k]]=c[a[k]]-1; } printf("\n sorted array:"); for(i=1;i<=n;i++) printf(" %d\t",b[i]); getch(); } |
Output
Read Also