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;
    }
}