I don't know how to make this radix sort in descending order. Please can you help me to do that? Thank you in advance. I tried to calculate cumulative frequencies in reverse order. But I didn't succeed

void countingSort(int *vector, int size, int place) {
  int output[size   1];
  int max = (*vector / place) % 10;

  for (int i = 1; i < size; i  ) {
    if (((*(vector   i) / place) % 10) > max)
      max = *(vector   i);
  }
  int count[max   1];

  for (int i = 0; i < max;   i)
    count[i] = 0;

  for (int i = 0; i < size; i  )
    count[(*(vector   i) / place) % 10]  ;

  for (int i = 1; i < 10; i  )
    count[i]  = count[i-1];

  for (int i = size - 1; i >= 0; i--) {
    output[count[(*(vector   i) / place) % 10] - 1] = *(vector   i);
    count[(*(vector   i) / place) % 10]--;
  }

  for (int i = 0; i < size; i  )
    *(vector   i) = output[i];
}

void radixsort(int *vector, int size) {
  int max = getMax(vector, size);

  for (int place = 1; max / place > 0; place *= 10)
    countingSort(vector, size, place);
}

CodePudding user response：

You just need to reverse your offsetting loop in countingSort (where you adjust the 'count' values to calculate the correct spot in the output array to place the values with that digit):

for (int i = max; i > 0; i--)
    count[i-1]  = count[i];

Note that the loop you have is wrong (using 10 instead of max 1) so will fail any time max != 9. You also calculate max incorrectly in your initial loop (missing the / place) % 10). It would probably make things simpler to get rid of max in countingSort and just use a fixed size int count[10] -- the extra cost of a few extra digits worth of space when you don't need them is trivial.

There's also no reason to ever use the obfuscated *(vector i) -- just use vector[i], it is simpler and clearer.

So you end up with something like

void countingSort(int *vector, int size, int place, bool reverse) {
  int output[size];
  int count[10] = { 0 };

  for (int i = 0; i < size; i  )
    count[(vector[i] / place) % 10]  ;

  if (reverse) {
    for (int i = 9; i > 0; i--)
      count[i-1]  = count[i];
  } else {
    for (int i = 1; i < 10; i  )
      count[i]  = count[i-1];
  }

  for (int i = size - 1; i >= 0; i--)
    output[--count[(vector[i] / place) % 10]] = vector[i];

  for (int i = 0; i < size; i  )
    vector[i] = output[i];
}

also note that this will misbehave badly if you have negative values in your vector.