Saturday, March 2, 2013

What is counting sort? How to implement in C++?

Counting sort works when the input is known to be withing a range.

Create an array of size of input range. Go through each of the numbers in the input and increment the appropriate array value (input number is mapped as the index to array). Now overwrite the original input list with key values in the array and repeating as many times as that index counter holds.
  1. Best, Average and Worst case performance is O(N).
  2. Not a comparison sort.

Sample implementation of counting sort

#include <iostream>

using namespace std;

const int INPUT_SIZE = 20;
const int BUCKET_K = 10;

void print(int *input)
{
    for ( int i = 0; i < INPUT_SIZE; i++ )
        cout << input[i] << " ";
    cout << endl;
}

void countingsort(int* input)
{
    int CountArr[BUCKET_K] = { 0 };

    for (int i=0;i<INPUT_SIZE;i++)
    {
        CountArr[input[i]]++;
    }

    int outputindex=0;
    for (int j=0;j<BUCKET_K;j++)
    {
        while (CountArr[j]--)
            input[outputindex++] = j;
    }

}

int main()
{
    int input[INPUT_SIZE] = { 2, 4, 6, 4, 7, 1, 4, 9, 5, 3, 7, 2, 2, 6, 9, 3, 7, 3, 4, 4 };

    cout << "Input: ";
    print(input);
    countingsort(input);
    cout << "Output: ";
    print(input);
    return 0;
}

Output:-
Input: 2 4 6 4 7 1 4 9 5 3 7 2 2 6 9 3 7 3 4 4 
Output: 1 2 2 2 3 3 3 4 4 4 4 4 5 6 6 7 7 7 9 9 

0 comments :

Post a Comment

Contact Form

Name

Email *

Message *

Back to Top