Counting Sort

Counting Sort is a kind of sort which you can use, only when you have prior knowledge about the kind of data you are sorting. For counting sort, we need to know about the range of the give data eg: o – 100, 200 – 1000. We do counting sort in two steps:

1. Count the number of times an element/ integer has occured in the given list.
2. perform prefix on the count array.
2. Find the position of the element according to count of elements which are before to it.

Following is the example demostrating counting sort:

Input: 5 1 5 1 3
count:2 0 1 0 2
prefix – count: 2 2 3 3 5
Output: 1 1 3 5 5

To find the output array, we do the following:

1. pick the element from the input array. Let us pick 5 which occured first and call it X.
2. Find the integer which is placed at X in the prefix count array. i.e. position = prefixCount[X-1].
3. This is the position of the element in the output and decrement the value of in the prefix-count array.

Following is the C code for counting sort.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <limits.h>

void countingSort(int , int *);
void display(int, int *);
/* Main Method takes the input from the users and performs counting sort on the input_array */
void main() {
        int *input_array, size, index, ch;
        srand(time(NULL));
        printf("Enter the size of the array: ");
        scanf("%d", &size);
        input_array = (int *)malloc(sizeof(int) * size);
        printf("\n\n1. Random Number Generation\n2. User Input\nEnter choice from above: ");
        scanf("%d", &ch);
        if(ch == 1){ //Random Generation
                for(index=0; index<size; index++)
                        input_array[index] = rand()%99 + 1 ; //Will generate numbers in the range of 1 - 100.
        } else if (ch == 2) { //User Input
                printf("\nPlease enter value less than 100\n");
                for(index = 0; index<size; index++) {
                        printf("\nEnter the element to be sorted: ");
                        scanf("%d", &input_array[index]);
                        while(1) {
                                if (input_array[index] < 0 || input_array[index] > 100) {
                                                printf("Please enter only positive values and values less than 100 only:");
                                                scanf("%d", &input_array[index]);
                                }
                                else
                                        break;
                        }
                }
        }
        else {
                printf("\nPlease Enter correct Choice, re-run the program");
        }
        printf("\n\nRandomly Generated data is: ");
        display(size, input_array);
        countingSort(size, input_array);
}
void display(int size, int *array) {
        int index;
        for(index=0;index<size;index++)
                printf("%d ", array[index]);
}
void countingSort(int size, int *input_array) {
        int *count_array, *sorted_array, position, index;
        count_array = (int *)calloc(100, sizeof(int));
        sorted_array = (int *)malloc(sizeof(int) * size);

        for (index=0;index<size;index++) //Find number of times item has appeared.
                count_array[input_array[index]]++;
        for (index=1;index<100;index++) //Perform prefix sum on count_array.
                count_array[index] += count_array[index-1];
        for (index=0;index<size;index++) { //Find the position fo the element and palce element inthat position of sorted_array.
                position = count_array[input_array[index]]--;
                sorted_array[position-1] = input_array[index];
        }
        printf("\n\nSorted array is: ");
        display(size, sorted_array);
        printf("\n");
}

The code performs counting sort.
Output:
counting sort

Download code from here.

Advertisements

About Anuroop D

Very enthusiastic about technology and likes to share my knowledge through blogging. Has Bachelor's in Information Technology and currently pursuing my Master's in Computer Science.
This entry was posted in Algorithms, C and tagged , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s