CODEWITHSUNDEEP
c++algorithm
MATH000
MATH000

Reputation: 1103

Optimize counting sort?

Given that the input will be N numbers from 0 to N (with duplicates) how I can optimize the code bellow for both small and big arrays:

void countingsort(int* input, int array_size)
{
    int max_element = array_size;//because no number will be > N

    int *CountArr = new int[max_element+1]();

    for (int i = 0; i < array_size; i++)
        CountArr[input[i]]++;

    for (int j = 0, outputindex = 0; j <= max_element; j++)
        while (CountArr[j]--)
            input[outputindex++] = j;

    delete []CountArr;
}

Having a stable sort is not a requirement.

edit: In case it's not clear, I am talking about optimizing the algorithm.

Upvotes: 2

Views: 1242

Answers (2)

Stephen Quan
Stephen Quan

Reputation: 25926

IMHO there's nothing wrong here. I highly recommend this approach when max_element is small, numbers sorted are non sparse (i.e. consecutive and no gaps) and greater than or equal to zero.

A small tweak, I'd replace new / delete and just declare a finite array using heap, e.g. 256 for max_element.

int CountArr[256] = { }; // Declare and initialize with zeroes

As you bend these rules, i.e. sparse, negative numbers you'd be struggling with this approach. You will need to find an optimal hashing function to remap the numbers to your efficient array. The more complex the hashing becomes the benefit between this over well established sorting algorithms diminishes.

Upvotes: 1

Emerald Weapon
Emerald Weapon

Reputation: 2540

In terms of complexity this cannot be beaten. It's O(N) and beats standard O(NlogN) sorting by exploiting the extra knowledge that 0<x<N. You cannot go below O(N) because you need at least to swipe through the input array once.

Upvotes: 1

Related Questions