Counting sort
Counting sort is a linear time sorting algorithm used to sort items when they belong to a fixed and finite set. Integers which lie in a fixed interval, say k1 to k2, are examples of such items.
Algorithm
COUNTING-SORT(A,B,k) 1. let C[0..k] be a new array 2. for i = 0 to k 3. C[i] = 0 4. for j = 1 to A.length 5. C[A[j]] = C[A[j]] + 1 6. // C[i] now contains the number of elements equal to i . 7. for i = 1 to k 8. C[i] = C[i] + C[i - 1] 9. // C[i] now contains the number of elements less than or equal to i . 10.for j = A.length downto 1 11. B[C[A[j]]] = A[j] 12. C[A[j]] = C[A[j]] - 1
Counting sort Implementation
#include <stdio.h> #include <conio.h> void Counting_sort(int [], int, int); void main() { int n,i,k=0,A[15]; clrscr(); printf("\n\n \t\t\t----------Counting Sort----------\n\n\n"); 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] > k) { k = A[i]; } } Counting_sort(A, k, n); getch(); } 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("\t\t\t----Sorted Array Using Counting Sort----\n\n\n" ); printf("\nThe Sorted array is : "); for(i=1;i<=n;i++) { printf("\t"); printf("%d",B[i]); } }
Output
