Using Counting Sort with Negative values? (Descending Order)

Question

I have a counting sort working as it should for x > 0, which sorts my array in a descending order. However the logic of my implementation falls apart when considering negative numbers, since I am reaching into negative indexes in the helper array values. I was thinking of somehow using uint but I am not very familiar with it.

How can I over come this Using a Counting Sort.

static void countingSort(int[] arr)    
{
    int i, j, max = -1; // I think it falls apart about here 
    int[] values;

    for (i = 0; i < arr.Length; i++)
        if (arr[i] > max) max = arr[i];

    values = new int[max + 1];

    //Here it reaches for a negative index when i = 2,looking for -6.            
    for (i = 0; i < arr.Max(); i++)
        values[arr[i]]++; 

    i = 0; j = values.Length - 1;
    while (i < arr.Length)
    {
        if (values[j] > 0)
        {
            values[j]--;
            arr[i] = j;
            i++;
        }
        else j--;
    }
}

I know my problem is with the indexing of the helping array. And since I don't want to go on making arrays with negative indexes, I am a bit stumped.

Can you even do that in c# without implementing a whole class as a Indexer? I know you can do that in C, its well defined:

From C99 §6.5.2.1/2: The definition of the subscript operator [] is that E1[E2] is identical to (*((E1)+(E2))).

My test array is { 8, 5, -6, 7, 1, 4 }

My expected output is { 8, 7, 5, 4, 1, -6 }

Answer 1

In your example, you already are scanning the input array to find the maximum value. What's missing is that you are not also scanning the input array to find the minimum value. If you add that, then knowing the minimum value, you can offset the range of array indexes to allow for negative numbers (and even potentially to reduce the size of the array if dealing with only positive numbers).

That would look like this:

static void Sort(int[] array)
{
    int min = int.MaxValue, max = int.MinValue;

    for (int i = 0; i < array.Length; i++)
    {
        if (array[i] < min)
        {
            min = array[i];
        }

        if (array[i] > max)
        {
            max = array[i];
        }
    }

    int[] counts = new int[max - min + 1];

    for (int i = 0; i < array.Length; i++)
    {
        counts[array[i] - min]++;
    }

    int k = 0;

    for (int j = max; j >= min; j--)
    {
        for (int i = 0; i < counts[j - min]; i++)
        {
            array[k++] = j;
        }
    }
}

Note that one significant disadvantage to this kind of sort is the need to maintain a contiguous array holding all of the possible values in the input. Even if you only have two elements in the input array, if their values are int.MinValue and int.MaxValue, you would need an intermediate array that's 16GB large (ignoring for a moment that you'll get into trouble with the integer math calculating the length of the array using just int).

An alternative is to use a dictionary to store the counts. This allows you to avoid allocating memory for input values that aren't present. It also happens to allow you to only have to scan the input once, instead of twice (but the cost of this is that you're dealing with a data structure that will have to reallocate its underlying storage as you add new elements, so the algorithmic complexity isn't really reduced much).

That would look like this:

static void Sort(int[] array)
{
    int min = int.MaxValue, max = int.MinValue;

    Dictionary<int, int> counts = new Dictionary<int, int>();

    for (int i = 0; i < array.Length; i++)
    {
        if (array[i] < min)
        {
            min = array[i];
        }

        if (array[i] > max)
        {
            max = array[i];
        }

        int count;

        // If the key is not present, count will get the default value for int, i.e. 0
        counts.TryGetValue(array[i], out count);
        counts[array[i]] = count + 1;
    }

    int k = 0;

    for (int j = max; j >= min; j--)
    {
        int count;

        if (counts.TryGetValue(j, out count))
        {
            for (int i = 0; i < count; i++)
            {
                array[k++] = j;
            }
        }
    }
}