Question

Radix sort
Come up with an unsorted array of numbers (integer array). Sort the numbers in ascending order and descending order and display them using radix sort.

First sort in ascending, then reset the array to its original order and finally sort the array again in descending order.

C++ program
thanks

Answer 1

/*
 *  C++ Program for radix sort ascending and descending
 */

#include <bits/stdc++.h>
using namespace std;
#define MAX 50

void RadixSortAsc(int a[], int n)
{
  int i, m = 0, exp = 1, b[MAX];
  
  for (i = 0; i < n; i++)
  {
    if (a[i] > m)
      m = a[i];
  }
  
  while (m/exp>0)
  {
    int bucket[10] = {0};
    for (i = 0; i < n; i++)
      bucket[a[i]/exp%10]++;
    for (i = 1; i < 10; i++)
      bucket[i] += bucket[i-1];
    for (i = n-1; i >= 0; i--)
      b[--bucket[a[i]/exp%10]] = a[i];
    for (i = 0; i < n; i++){
      a[i] = b[i];
    }
    exp *= 10;
  }
}

void RadixSortDesc(int a[], int n)
{
  int i, m = 0, exp = 1, b[MAX];
  
  for (i = 0; i < n; i++)
  {
    if (a[i] > m)
      m=a[i];
  }
  
  while (m/exp>0)
  {
    int bucket[10] = {0};
    for (i = 0; i < n; i++)
      bucket[9-a[i]/exp%10]++;              // this line is changed for desc
    for (i = 1; i < 10; i++)
      bucket[i] += bucket[i-1];
    for (i = n-1; i >= 0; i--)
      b[--bucket[9-a[i]/exp%10]] = a[i];    // this line is changed for desc
    for (i = 0; i < n; i++){
      a[i] = b[i];                          // this line is changed for desc
    }
    exp *= 10;
  }
}

void print(int arr[], int n)
{
  for (int i = 0; i < n; i++)
    cout << arr[i] << " ";
}

int main()
{
  int arr[] = {70, 40, 50, 90, 10, 20, 0, 60};
  int n = sizeof(arr)/sizeof(arr[0]);

  cout << "Before -" << endl;
  print(arr, n);
  cout << endl;

  cout << "Ascending Sort -" << endl;
  RadixSortAsc(arr, n);
  print(arr, n);
  cout << endl;

  cout << "Descending Sort -" << endl;
  RadixSortDesc(arr, n);
  print(arr, n);
  cout << endl;
  
  return 0;
}