Related Tags

counting sort

# What is a counting sort algorithm?

Counting sort is one of the most famous sorting algorithms â€“ itâ€‹ performs some arithmetic calculations in order to get the perfect output sequence.

## Algorithm

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