javaalgorithmsortingradix-sortcounting-sort

Getting radix/counting sort to work with negative numbers


I am getting into programming, pardon if I am missing something obvious. I have a basic LSD radix sort and counting sort pair. How would I go about converting this to work with negative numbers? Is it possible with this style of counting sort or do I need another?

void radixsort(int arr[], int n) {
   int m = getMaxElement(arr, n);//Find the maximum number in array.   

   for (int exp = 1; m/exp > 0; exp *= 10)
      CountSort(arr, n, exp);
}

void CountSort(int arr[], int n, int exp) {

   int output[n];
   int i, c[10] = {0}; // store the number of times in c[]

   for (i = 0; i < n; i++)
      c[ (arr[i]/exp)%10 ]++;


   for (i = 1; i < 10; i++)
      c[i] +=c[i - 1];
   // Making the output array
   for (i = n - 1; i >= 0; i--) {
      output[count[ (arr[i]/exp)%10 ] - 1] = arr[i];
      c[ (arr[i]/exp)%10 ]--;
}

   for (i = 0; i < n; i++)
      arr[i] = output[i];
}

Solution

  • You can treat the sign as a separate digit, the most significant one. So your last pass would only have two buckets - negative and non-negative.

    One thing you need to do differently is to move the numbers from the negative bucket to the final array in the reverse order (because the previous passes ignore the sign, so negative numbers are sorted by their absolute value, which means in reverse order).