Как заставить основную / счетную сортировку работать с отрицательными числами

Question

Я вхожу в программирование, простите, если я упускаю что-то очевидное. У меня есть базовая c LSD основанная на сортировке и подсчете пара. Как бы я go о преобразовании этого для работы с отрицательными числами? Это возможно с таким стилем подсчета или мне нужен другой?

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

Answer 1

Вы можете рассматривать знак как отдельный ди git, самый значимый. Таким образом, ваш последний проход будет иметь только два сегмента - отрицательный и неотрицательный.

Одна вещь, которую вам нужно сделать по-другому, это переместить числа из отрицательного сегмента в конечный массив в обратном порядке (поскольку предыдущие проходы игнорируют знак, поэтому отрицательные числа сортируются по их абсолютному значению, которое означает в обратном порядке).