Trusted answers to developer questions

What is a counting sort algorithm?

Get Started With Machine Learning

Learn the fundamentals of Machine Learning with this free course. Future-proof your career by adding ML skills to your toolkit — or prepare to land a job in AI or Data Science.

#include<iostream>
#include<algorithm>
using namespace std;
// function for printing an array.
void printArr(int *array, int size) {
   for(int i = 0; i < size; i++)
      cout << array[i] << " ";
   cout << endl;
}
// function for calculating maximum element.
int findMax(int array[], int size) {
   int max = array[0];
   for(int i = 1; i < size; i++) {
      if(array[i] > max)
         max = array[i];
   }
   return max; 
}
// function for the count sort algorithm
void countSort(int *array, int size) {
   int output[size];
   
   int max = findMax(array, size);
   int count[max+1]; 
   for(int i = 0; i <= max; i++)
      count[i] = 0;  //initialize frequencies array to all zero
   for(int i = 0; i < size; i++)
      count[array[i]]++;   //fill the array with the count of each number
   for(int i = 1; i <= max; i++)
      count[i] += count[i-1]; //find cumulative frequency
   for(int i = size - 1 ; i>=0; i--) {
      output[count[array[i]]-1] = array[i];
      count[array[i]] -= 1;   //decrease count for same numbers
   }
   for(int i = 0; i < size; i++) {
      array[i] = output[i];   //store output array to main array
   }
}
int main() {
   int arr[] = {1, 5, 9, 8, 1, 3};
   int n = 6;
   cout << "Array before Sorting: ";
   printArr(arr, n);
   countSort(arr, n);
   cout << "Array after Sorting: ";
   printArr(arr, n);
}

Counting sort

How to handle negative values and ranges with a larger minimum value?

We can see one drawback here, that if the minimum value is $1000$ , the first $1000$ indexes of the frequency array will not be used and it will increase the space complexity. Let’s do a little trick here.

Find the minimum value of the array and subtract it from all elements of the array. By doing this, the range of the array will be always from $0$ to ( $maximum - minimum$ ).
Apply counting sort.
Add the number we subtracted in the first step.

Now we can handle the negative integer values as well. See the following code:

#include<iostream>
#include<algorithm>
using namespace std;
// function for printing an array.
void printArr(int *array, int size) {
   for(int i = 0; i<size; i++)
      cout << array[i] << " ";
   cout << endl;
}
// function for calculating maximum element.
int findMax(int array[], int size) {
   int max = array[0];
   for(int i = 1; i < size; i++) {
      if(array[i] > max)
         max = array[i];
   }
   return max; 
}
// function for calculating minimum element.
int findMin(int array[], int size) {
   int min = array[0];
   for(int i = 1; i < size; i++) {
      if(array[i] < min)
         min = array[i];
   }
   return min; 
}
// function for the count sort algorithm
void countSort(int *array, int size) {
   int output[size];
   int min = findMin(array, size); 
   for(int i = 0; i < size; i++)
      array[i]-=min; // subtracting minimum value from the array to start range from 0
   int max = findMax(array, size);
   int count[max+1]; 
   for(int i = 0; i<=max; i++)
      count[i] = 0;  //initialize frequencies array to all zero
   for(int i = 0; i < size; i++)
      count[array[i]]++;   //fill the array with the count of each number
   for(int i = 1; i<=max; i++)
      count[i] += count[i-1]; //find cumulative frequency
   for(int i = size - 1 ; i>=0; i--) {
      output[count[array[i]]-1] = array[i];
      count[array[i]] -= 1;   //decrease count for same numbers
   }
   for(int i = 0; i < size; i++) {
      array[i] = output[i] + min; //store output array to main array with the actual values
   }
}
int main() {
   int arr[] = {1, 5, 9, 8, -1, -3};
   int n = 6;
   cout << "Array before Sorting: ";
   printArr(arr, n);
   countSort(arr, n);
   cout << "Array after Sorting: ";
   printArr(arr, n);
}

Optimized counting sort

RELATED TAGS

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments

What is a counting sort algorithm?

Algorithm

Code

Explanation

How to handle negative values and ranges with a larger minimum value?

Time complexity

Space complexity