# Counting Sort

Sorting Algorithm

Share

In this tutorial we will be learning about Counting sort algorithm.

It is a sorting algorithm in which we sort a collection of elements based on numeric keys. In this algorithm we don't compare elements while sorting. It is often used as a subroutine in other sorting algorithm.

## C Code

``````#include <stdio.h>

//const
#define MAX 10

//function declaration
void display(int arr[], int size);
int getMax(int arr[], int size);
void countingSort(int arr[], int size);

int main() {
//unsorted elements
int arr[] = {10,15,1,60,5,100,25,50};

//size of the array
int n = sizeof(arr)/sizeof(arr[0]);

//output unsorted elements
display(arr, n);

//sort the elements
countingSort(arr, n);

//display sorted elements
display(arr, n);

return 0;
}

void display(int arr[], int size) {
int i;
for(i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}

int getMax(int arr[], int size) {
int i, max = arr[0];
for(i = 1; i < size; i++) {
if(arr[i] > max) {
max = arr[i];
}
}
return max;
}

void countingSort(int arr[], int size) {
int i, max, temp[MAX], count[10], expo = 1;

//get the max value element in the unsorted array
max = getMax(arr, size);

while(max / expo > 0) {
//reset count
for(i = 0; i < 10; i++) {
count[i] = 0;
}

//save count of the occurrence
for(i = 0; i < size; i++) {
count[ (arr[i] / expo) % 10 ]++;
}

//set count to contain the actual position of the digits
for(i = 1; i < size; i++) {
count[i] += count [i - 1];
}

//build the result
for(i = size - 1; i >= 0; i--) {
temp[ count[ (arr[i]/expo) % 10 ]  - 1] = arr[i];
count[ (arr[i]/expo) % 10 ]--;
}

//copy the result to arr
for(i = 0; i < size; i++) {
arr[i] = temp[i];
}

//increase expo, 10^x
expo *= 10;
}
}
``````
Share