C++ Radix sort , sortujący malejąco

Question

Witam! Ostatnio sprawdzałem w internecie czy jest jakiś algorytm sortowania, który jest lepszy od quicksort. Znalazłem Radix sort , który wydaje się być świetny , ale mam tutaj kod który właśnie używa tego algorytmu , tylko że ten kod sortuje liczby w tablicy rosnąco , a ja chciałbym żeby sortował malejąco. W takim razie jakie musiałbym wprowadzić zmiany w poniższym kodzie aby sortował właśnie malejąco?

void radixsort(int *input,int n)
{
  int i;

  // find the max number in the given list.
  // to be used in loop termination part.
  int maxNumber = input[0];
  for (i = 1; i < n; i++)
  {
    if (input[i] > maxNumber)
      maxNumber = input[i];
  }

  // run the loop for each of the decimal places
  int exp = 1;
  int *tmpBuffer = new int[n];
  while (maxNumber / exp > 0)
  {
    int decimalBucket[10] = {  0 };
    // count the occurences in this decimal digit.
    for (i = 0; i < n; i++)
      decimalBucket[input[i] / exp % 10]++;

    // Prepare the position counters to be used for re-ordering the numbers
    // for this decimal place.
    for (i = 1; i < 10; i++)
      decimalBucket[i] += decimalBucket[i - 1];

    // Re order the numbers in the tmpbuffer and later copy back to original buffer.
    for (i = n - 1; i >= 0; i--)
      tmpBuffer[--decimalBucket[input[i] / exp % 10]] = input[i];
    for (i = 0; i < n; i++)
      input[i] = tmpBuffer[i];

    // Move to next decimal place.
    exp *= 10;

  }
}

 

Z góry dziękuje za pomoc!

Comments

Więc podsumując , kod w pytaniu sortuje rosnąco , a kod poniższy malejąco:

void radixsort(int *input,int n)
{
  int i;

  // find the max number in the given list.
  // to be used in loop termination part.
  int maxNumber = input[0];
  for (i = 1; i < n; i++)
  {
    if (input[i] > maxNumber)
      maxNumber = input[i];
  }

  // run the loop for each of the decimal places
  int exp = 1;
  int *tmpBuffer = new int[n];
  while (maxNumber / exp > 0)
  {
    int decimalBucket[10] = {  0 };
    // count the occurences in this decimal digit.
    for (i = 0; i < n; i++)
      decimalBucket[input[i] / exp % 10]++;

    // Prepare the position counters to be used for re-ordering the numbers
    // for this decimal place.
    for (i = n-2; i >= 0; i--)                        
      decimalBucket[i] += decimalBucket[i + 1];        

    // Re order the numbers in the tmpbuffer and later copy back to original buffer.
    for (i = n - 1; i >= 0; i--)
      tmpBuffer[--decimalBucket[input[i] / exp % 10]] = input[i];
    for (i = 0; i < n; i++)
      input[i] = tmpBuffer[i];

    // Move to next decimal place.
    exp *= 10;

  }
}

 

PS.

Jakby co to teraz zauważyłem, że tablica tmpBuffer nie jest zwalniana, więc jak ktoś chce skopiować kod to niech lepiej pamięta aby dodać "delete[] tmpBuffer" na końcu funkcji.

Answer 1

Musiałbyś zmienić w 33 linijce

input[i] = tmpBuffer[i];

na:

input[n-i-1] = tmpBuffer[i];

 

Comments

Nie działa :(

Jak napisałem w main taki kod:

int tab[10] = {1 , 2, 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10};

    for(int i=0;i<10;++i)
        cout << tab[i] << " ";

    cout << "   <- przed sortowaniem";
    cout << "\n\n";

    radixsort(tab,10);

    for(int i=0;i<10;++i)
        cout << tab[i] << " ";

     cout << "   <- po sortowaniu";

to wynik był taki:

---

Faktycznie, przyjrzałem się teraz dokładniej. Trzeba zmodyfikować pętle z 26 linijki.

for (i = n-2; i >=0; i--)
      decimalBucket[i] += decimalBucket[i + 1];

 

---

Dzięki , teraz wszystko działa! Bardzo dziękuje!