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 deﬁnition 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 }

Well, C# does not do "pointer math" in its indexer like C does, so no they're not equivalent. — D Stanley
– D Stanley, Commented Nov 7, 2016 at 23:33

luckyguy73 · Accepted Answer · 2020-10-03 18:18:43Z

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;
            }
        }
    }
}

Fadi Banna · Accepted Answer · 2016-11-08 00:20:51Z

It actually can be done in a pretty easy shift here is you sort updated:

    static void countingSort(int[] arr)
    {
        int i, j, max = -1; 
        int[] values;
        //get the highest absolute value to determine the size of the array 
        for (i = 0; i < arr.Length; i++)
            if (Math.Abs(arr[i]) > max) max = Math.Abs(arr[i]);
        //create double the max size array
        values = new int[max*2 + 1];

        //when reaching a value make a shift of max size            
        for (i = 0; i < arr.Length; i++)
            values[arr[i]+max]++;

        i = 0; j = values.Length - 1;
        while (i < arr.Length)
        {
            if (values[j] > 0)
            {
                values[j]--;
                //shift back when putting in the sorted array
                arr[i] = j-max;
                i++;
            }
            else j--;
        }

    }

this way lets say you have an array of {-4,3,2} you will create an array of size (4*2+1)=9 cause the highest absolute value is the -4 ,and the shift would be 4 so the -4 will sit in index 0 and the 2 for example will sit in index 6 of the values array,this way you avoid the problem and get the result you want.

Carlos E Rodriguez · Accepted Answer · 2016-11-07 23:57:15Z

See this. https://en.wikipedia.org/wiki/Counting_sort.

The problem is with "values[arr[i]]++". If a value in arr[i] returns a negative number, it will not work.

One possibility is to write a function "Hash-key(arr[i])" that takes any number in your array and converts that to a dictionary key value. you can write your own or use a library.

If you are using C# then the "System.Collections" have many classes to facilitate dictionary indexing.

using System;
using System.Collections;
public class SamplesArrayList  {

   public static void Main()  {

   // Creates and initializes a new ArrayList.
   ArrayList myAL = new ArrayList();
   myAL.Add("Hello");
   myAL.Add("World");

myAL.Add("!");

Your helper would be loaded with the data in the source "arr" array. Hope this helps.

Anirudh Jhunjhunwala · Accepted Answer · 2021-12-09 02:32:44Z

0

One way to solve the array containing negative numbers is:

keep all the negative numbers separate in another array, make them positive(simply negate the signs), use counting sort on them, and reverse them and put back the negative signs. Along with this, separately do the counting sort for positive numbers and merge the negative ones along with the positive ones. And you got your answer!

answered Dec 9, 2021 at 2:32

Anirudh Jhunjhunwala

11 gold badge1 silver badge1 bronze badge

Collectives™ on Stack Overflow

Using Counting Sort with Negative values? (Descending Order)

4 Answers 4

Comments

Comments

myAL.Add("!");

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

myAL.Add("!");

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related