Count sort implementation

Question

Is this a proper Count sort implementation?
Code and style improvements?

It does not support negative and that should be improved. A large input could cause out of memory.

Some of the array index is different as the WIKI is 1 based and these arrays are zero based.

public static void CountSort(int[] arr)
{
    int max = -1;
    foreach(int i in arr)
    {
        if (i < 0)
        {
            throw new IndexOutOfRangeException(" < 0 ");
        }
        max = Math.Max(max, i);
    }

    int n = arr.Length;

    // The output character array that will have sorted arr
    int[] output = new int[n];

    // Create a count array to store count of inidividul
    // characters and initialize count array as 0
    int[] count = new int[max+1];
    for (int i = 0; i <= max; ++i)
        count[i] = 0;

    // store count of each character
    foreach (int i in arr)
        count[i]++;

    // Change count[i] so that count[i] now contains actual
    // position of this character in output array
    for (int i = 1; i <= max; ++i)
        count[i] += count[i - 1];

    // Build the output character array
    for (int i = 0; i < n; ++i)
    {
        output[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }

    // Copy the output array to arr, so that arr now
    // contains sorted characters
    for (int i = 0; i < n; ++i)
        arr[i] = output[i];
}

//test
int[] ar = new int[] { 0, 0, 0, 0 }; 
CountSort(ar);
foreach (int i in ar)
    Debug.WriteLine(i);
Debug.WriteLine("");

ar = new int[] { 5, 5, 5, 5 }; 
CountSort(ar);
foreach (int i in ar)
    Debug.WriteLine(i);
Debug.WriteLine("");

ar = new int[] {};
CountSort(ar);
foreach (int i in ar)
    Debug.WriteLine(i);
Debug.WriteLine("");

ar = new int[] { 90, 90, 71, 82, 93, 75, 81, 0, 12, 54, 36, 13, 102, 99, 34, 103, 78, 196, 52, 5, 215 };
CountSort(ar);
foreach (int i in ar)
    Debug.WriteLine(i);
Debug.WriteLine("");

Just a small note: some documentation about when (or when not) to use this method, and what its input restrictions are, would be helpful. Negative input not being supported and large memory consumption or out-of-memory problems for large values are a bit surprising, after all. — Pieter Witvoet
– Pieter Witvoet, Commented Jul 31, 2017 at 12:53
When to use is not really what code review is about but OK. I did not really think about it not supporting negative until I tested. — paparazzo
– paparazzo, Commented Jul 31, 2017 at 13:33
With 'when to use' I meant that this is not a general purpose sort algorithm, so it'd be helpful to document that it's specifically designed for inputs with relatively small values (or variations, if you also look for the minimum value). — Pieter Witvoet
– Pieter Witvoet, Commented Jul 31, 2017 at 13:51

janos · Accepted Answer · 2017-07-30 17:47:03Z

Limitations

Being able to sort in \$O(n)\$, counting sort can be very efficient, but with the right kind of data. Just keep in mind that it won't work well when the variation in values is very large.

Optimizations and extensions

The implementation checks the maximum value, so the array of counts will use that much space. You could reduce the amount of space used by finding the minimum too. That way the size of the array of counts could be max - min instead of max. That will of course require to use the min as an offset both when building the array of counts, and when writing the output.

Related to that, the current implementation doesn't support negative values in the input. But it could, by using the minimum value as an offset. In fact, by applying the optimization above, negative numbers will be automatically supported.

Unnecessary storage and mutations

There's no need for the temporary output array, and for modifying the content of count to contain positions. Once you have the array of counts, you can directly overwrite the target array, reducing the amount of code and simplifying the implementation.

for (int countIndex = 0, outIndex = 0; countIndex < count.Length; ++countIndex)
{
    for (int i = 0; i < count[countIndex]; ++i)
    {
        arr[outIndex++] = countIndex;
    }
}

Unnecessary array initialization

int[] arrays are initialized with zeros, no need to manually set the content to zeros.

Style tips

It's recommended to always use braces with loops and conditionals.

Testing

It's better to use a proper unit testing framework that gives you simple pass-or-fail results, rather than reading the output and verifying manually that it's actually correct.

Totally agree on the { } I should clean that up prior to posting on this site. And I agree with unit testing. If I have to do it eventually I might as well do it before posting. — paparazzo
– paparazzo, Commented Jul 30, 2017 at 17:32
I am with you but if it is int I am not sure space could ever be an issue. — paparazzo
– paparazzo, Commented Jul 30, 2017 at 22:49
@Paparazzi if my calculations are correct, then If the input contains 2 numbers, 0 and max-int, then the array of counts will allocate 8G ;-) — janos
– janos, Commented Jul 31, 2017 at 6:12

Heslacher · Accepted Answer · 2017-07-31 04:59:16Z

4

At the very top of the method you have

if (i < 0)
{
    throw new IndexOutOfRangeException(" < 0 ");
}

which is plainly throwing the wrong exception. IndexOutOfRangeException should be thrown if an index isn't in the range it should.

What you are after is the ArgumentOutOfRangeException.

answered Jul 31, 2017 at 4:59

Heslacher

51k5 gold badges83 silver badges177 bronze badges

Add a comment |

Stack Exchange Network

Count sort implementation

2 Answers 2

Limitations

Optimizations and extensions

Unnecessary storage and mutations

Unnecessary array initialization

Style tips

Testing

You must log in to answer this question.

Hot Network Questions