What is Count Sort? explain with an example

Counting Sort

Counting Sort is a non-comparison-based sorting algorithm that operates on integers, often used when the range of input values is known and relatively small. It counts the number of occurrences of each unique element in the input array and uses this information to place each element directly into its sorted position in the output array.

Counting Sort Algorithm

Determine the range: Find the minimum and maximum values in the input array to determine the range of input data.

Count occurrences: Create an auxiliary array, often called the count array, of size equal to the range of input data. Traverse the input array and count the occurrences of each unique element, storing these counts in the count array.

Cumulative sum: Modify the count array to represent the cumulative sum of counts. This step ensures that each element in the count array represents the number of elements less than or equal to its index.

Place elements: Iterate through the input array in reverse order. For each element, use the count array to determine its correct position in the output array. Decrement the count for that element in the count array after placing it in the output array to handle duplicate elements.

Copy back: Copy the elements from the output array back to the original array to obtain the sorted result.

Count sort example code

Here is a C source code of Count sorting with 10 integer elements. This code sorts the elements in ascending order.

 #include <stdio.h>

 void CountSort(int array[], int size) {

     int max = array[0];

     /* Find the max number in the array */

     for (int i = 1; i < size; i++) {

         if (array[i] > max)

             max = array[i];

     }

     /* Initialize the count array */

     int count[max + 1];

     for (int i = 0; i <= max; i++)

         count[i] = 0;

    /* Update the counts in the array */

     for (int i = 0; i < size; i++)

         count[array[i]]++;

     /* Cumulative sum */

     for (int i = 1; i <= max; i++)

         count[i] += count[i - 1];

     /* Place elements */

     int sorted[size];

     for (int i = size - 1; i >= 0; i--) {

         sorted[count[array[i]] - 1] = array[i];

         count[array[i]]--;

     }

     /* Copy the sorted array to original array */

     for (int i = 0; i < size; i++)

         array[i] = sorted[i];

 }

 int main(int argc, char * argv[]) {

     /* Unsorted array */

     int array[] = {4, 2, 2, 8, 3, 3, 1, 4, 7 , 10};

     int size = sizeof(array) / sizeof(array[0]);

     /* Call the count sort routine */

     CountSort(array, size);

     /* Print the sorted array */

     printf("Sorted array: ");

     for (int i = 0; i < size; i++)

         printf("%d ", array[i]);

     printf("\n");

     return 0;

 }

Output

Sorted array: 1 2 2 3 3 4 4 7 8 10

Advantages:

Counting Sort has a linear time complexity, making it highly efficient for sorting integer data with a limited range.

It is stable, meaning it preserves the relative order of equal elements, which is useful when sorting objects with multiple keys.

Counting Sort is simple to implement and understand, requiring only a few lines of code.

Disadvantages:

Counting Sort is not suitable for sorting data with large ranges or non-integer values. It requires extra space proportional to the range of input elements, which can be impractical for large ranges.

If the range of input data is significantly larger than the number of elements, Counting Sort becomes inefficient in terms of space usage.

Counting Sort is not an in-place sorting algorithm, as it requires additional space for the count array and the sorted array, leading to higher memory consumption compared to in-place sorting algorithms like Quicksort or Heapsort.

Time and Space Complexities:

Time Complexity: O(n + k), where n is the number of elements in the input array and k is the range of input data.

Space Complexity: O(n + k), where n is the number of elements in the input array and k is the range of input data.

In summary, Counting Sort is a simple and efficient sorting algorithm suitable for sorting integer data with a limited range. Its linear time complexity makes it faster than comparison-based sorting algorithms for such scenarios. However, it is not suitable for sorting data with large ranges or non-integer values due to its space requirements.