Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

counting sort

What is a counting sort algorithm?

Educative Answers Team

Counting sort is one of the most famous sorting algorithms – it​ performs some arithmetic calculations in order to get the perfect output sequence.

Algorithm

svg viewer

The above algorithm is illustrated in the example below:

1 of 5

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 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]]++;
   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);
}

RELATED TAGS

counting sort
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring