Counting Sort algorithm - take negative and positive integer as input (using Map is not allowed)

Question

As you can see in this code I just did how to sort positive integer numbers using counting sort. but my requirement is I have to take the negative and positive numbers as input then have to sort the array using counting sort. finding the lowest value in the array then taking input is not allowed. I don't know what will be the logic and solution for this.

note: if I take any negative number in my input. the output shows 0 for that value.

Input: 9, 8, 6, -7, 2, 1

output: -7, 1, 2, 6, 8, 9

int k=0;
void Counting_Sort(int A[],int B[],int n)
{
    int C[k+1];
    for(int i=0; i<=k; i++)
    {
        C[i]=0;
    }
    for(int j=1; j<=n; j++)
    {
        C[A[j]]++;
    }
    for(int i=1; i<=k; i++)
    {
        C[i]+=C[i-1];
    }
    for(int j=n; j>=1; j--)
    {
        B[C[A[j]]]=A[j];
        C[A[j]]=C[A[j]]-1;
    }
}

// Driver code

int main()
{
    int n;
    cout<<"Enter the size of the array :";
    cin>>n;
    int A[n],B[n];
    for(int i=1; i<=n; i++)
    {
        cin>>A[i];
        if(A[i]>k)
        {
            /*It will modify k if an element
            occurs whose value is greater than k*/
            k=A[i];
        }
    }
    Counting_Sort(A,B,n);
    /*It will print the sorted sequence on the
    console*/
    for(int i=1; i<=n; i++)
    {
        cout<<B[i]<<" ";
    }
    cout<<endl;
    return 0;
}

Answer 1

There's a bit of constraint on this problem, but this can be solve by reversing the negative number back to a positive one, and storing negatives and positives in 2 different arrays. Then you can print the negative array first, after that print the positive array:

#include <iostream>
#include <cstring>
using namespace std;

const int maxval = 10000; //maximum absolute value of each element, you can change this

int positiveArr[maxval+1], negativeArr[maxval+1]; //positive and negative array

int main()
{
    int n; cin >> n;
    memset(positiveArr, 0, sizeof(positiveArr)); //set all value to 0
    memset(negativeArr, 0, sizeof(negativeArr)); //set all value to 0

    for (int i = 1; i <= n; i++)
    {
        int x; cin >> x; //input number;
        if (x >= 0) //if x is non-negative
        {
            positiveArr[x]++; //add count of x
        }
        else
        {
            negativeArr[-x]++; //add count of -x
        }
    }

    for (int i = maxval; i >= 1; i--) //printing the negative array
    {
        if (negativeArr[i] > 0)
        {
            for (int j = 1; j <= negativeArr[i]; j++) {cout << -i << " ";}
        }
    }

    for (int i = 0; i <= maxval; i++) //printing the positive array
    {
        if (positiveArr[i] > 0)
        {
            for (int j = 1; j <= positiveArr[i]; j++) {cout << i << " ";}
        }
    }
    return 0;
}

Result:

6
9 8 6 -7 2 1
-7 1 2 6 8 9

Another test:

19
-7 -9 0 1 -1 4 -3 -2 4 9 1 -9 -7 1 0 9 -7 -2 12
-9 -9 -7 -7 -7 -3 -2 -2 -1 0 0 1 1 1 4 4 9 9 12

Answer 2

There is a simple solution for this too. Just add maxValue (assuming this is the maximum absolute value numbers can have) to all elements, sort them with the count sort, then subtract maxValue to get back the original values. Addition makes all of them non-negative.