Tutorial 31

 ---- 31 Counting sort

#include<iostream>

using namespace std;

void display(int *array, int size)

 {

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

      cout << array[i] << " ";

   cout << endl;

}

int getMax(int array[], int size) 

{

   int max = array[1];

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

      if(array[i] > max)

         max = array[i];

   }

   return max; //the max element from the array

}

void countSort(int *array, int size)

 {

   int output[size+1];

   int max = getMax(array, size);

   

   //create count array (max+1 number of elements)

   int count[max+1]; 

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

      count[i] = 0; //initialize count array to all zero

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

      count[array[i]]++; //increase number count in count array.

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

      count[i] += count[i-1]; //find cumulative frequency

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

   {

      output[count[array[i]]] = array[i];

      count[array[i]] -= 1; //decrease count for same numbers

   }

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

      array[i] = output[i]; //store output array to main array

   }

}

int main() {

   int n;

   int arr[] = {2, 5, 6, 2, 3, 10, 3, 6, 7, 8};

   n = sizeof(arr)/sizeof(arr[0]);

   cout << "Array before Sorting: ";

   display(arr, n);

   countSort(arr, n);

   cout << "Array after Sorting: ";

   display(arr, n);

}