Counting Sort in C

February 7, 2024

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 for Counting Sort in C

Run 
// Counting sort in C programming
#include<stdio.h>
#define MAX 255

void countSort(int array[], int size)
{
    int output[MAX];
    int count[MAX];
    int max = array[0];

    // Here we find the largest item in the array
    for (int i = 1; i < size; i++) { if (array[i] > max)
            max = array[i];
    }

    // Initialize the count for each element in array to 0
    for (int i = 0; i <= max; ++i)
	{
        count[i] = 0;
    }

    // For each element we store the count
    for (int i = 0; i < size; i++)
	{
        count[array[i]]++;
    }

    // Store the cummulative count of each array
    for (int i = 1; i <= max; i++)
	{
		count[i] += count[i - 1];
	}
	
	// Search the index of each element of the actual array in count array, and
	// place the elements in output array
	for (int i = size - 1; i >= 0; i--) 
    {
        output[count[array[i]] - 1] = array[i];
        count[array[i]]--;
    }

    // Transfer the sorted items into actual array
    for (int i = 0; i < size; i++)
	{
        array[i] = output[i];
    }
}

// printing items of the array
void display(int array[], int size)
{
    for (int i = 0; i < size; i++)
        printf("%d ",array[i]);
    printf("\n");
}

// Driver code
int main() {
    int array[] = {2, 5, 2, 8, 1, 4, 1};
    int n = sizeof(array) / sizeof(array[0]);
  
    countSort(array, n);
  
    display(array, n);

    return 0;
}

Output:

1 1 2 2 4 5 8

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