Counting Sort in C

Counting Sort in C

Counting Sort, is an integer sorting algorithm, is a sorting technique in which we sort a collection of elements based on numeric keys between the specific range. In the counting algorithm we don’t compare element while sorting.it is often used as a subroutine in other sorting algorithm. By counting It operates the no. of objects having each distinct key value, after this it perform some arithmetic to calculate the position of each key value in output sequence.

It is used as a subroutine in another sorting algorithm for example radix sort.

If we  compare  counting sort  to bucket sort then we see that bucket sort  requires a large amount of preallocated memory or linked list and dynamic array  to hold the sets of items within each bucket, whereas counting sort instead stores a single number per bucket.

  • Time complexity of counting sort is O((n).

 

Counting Sort in c

Algorithm of Counting Sort

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 length[A]
5- do C[A[j]] <- C[A[j]]+1
    // C[i] now contains the number of elements equal to i.
6- for i<-1 to k
7-do C[i]<- C[i]+C[i-1]
      // C[i] now contains the number of elements less than or equal to i.
8- for j<- length[A] down to 1
9-do B[C[A[j]]]<- A[j]
10- C[A[j]]<-C[A[j]]-1.

 

Counting sort in c 1

Execution of Counting Sort
According to algorithm let us take an example

Step 1- 
  i=0 to 6             since  k=6(Largest element in array A)
  C[i]<-0

Step 2-
  j=1 to 10            since,length[A]=10
 C[A[j]]<-C[A[j]]+1

For j=1
     C[A[1]]<-C[1]+1= 0+1 =1
     C[1]<-1

For j=2
    C[A[2]]<-C[6]+1= 0+1 =1
    C[6]<-1

similarly for j=5,6,7,8,9,10

Counting sort in c 2

Step 3-
For i= 1 to 6
    C[i]<-C[i]+C[i-1]

For i=1
   C[1]<-C[1]+C[0]
   C[1]<-1+0 = 1

For i=2
     C[2]<-C[2]+C[1]
    C[1]<-1+0 = 1

Similarly for i=4,5,6

Step 4-
For j=10 to 1
   B[C[A[j]]]<-A[j]
   C[A[j]]<-C[A[j]]-1

Counting sort in c end

                                                          B= 1 3 3  3 4 4 5 6 6 

Program of Counting Sort in C

      //sorting in c
    //counting sort
#include
    //function for counting sort
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 : ");
    // printing the output
  for (i = 1; i <= n; i++)
  printf("%d ", b[i]);
}
  /* End of counting_sort() */
  // main function
  int main()
{
int n, k = 0, a[15], i;
  printf("Enter the number of input : ");
    // user 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];
}
}
// function calling
   counting_sort(a, k, n);
   printf("\n");
   return 0;
}

Sorting

Sorting algorithms are easy to learn but are really important for college semester exams and companies offering package between 3 – 6 LPA would ask direct searching questions in online test/ interviews.

Data Structures and Algorithm Learn Sorting