Answer:
// Radix Sort
#include<iostream>
using namespace std;
// function to get max value
int getMaximum(int array[], int n)
{
int max = array[0];
for (int i = 1; i < n; i++)
if (array[i] > max)
max = array[i];
return max;
}
// function to get min value
int getMinimum(int array[], int n)
{
int mn = array[0];
for (int i = 1; i < n; i++)
if (array[i] <mn)
mn= array[i];
return mn;
}
//counting sort
void counterSort(int array[], int n, int expo)
{
int out[100]; // out max
int i, count[10] = {0};
// Store count of occurrences in count[]
for (i = 0; i < n; i++)
count[ (array[i]/expo)%10 ]++;
// Change count[i] so that count[i] now contains actual
// position of this digit in out[]
for (i = 1; i < 10; i++)
count[i] += count[i - 1];
// construct the out max
for (i = n - 1; i >= 0; i--)
{
out[count[ (array[i]/expo)%10 ] - 1] = array[i];
count[ (array[i]/expo)%10 ]--;
}
for (i = 0; i < n; i++)
array[i] = out[i];
}
void counterSortDesc(int array[], int n, int expo)
{
int out[100]; // out max
int i, count[10] = {0};
// Store count of occurrences in count[]
for (i = 0; i < n; i++)
count[ (array[i]/expo)%10 ]++;
for (i = 10; i >=1; i--)
count[i] += count[i - 1];
// construct out max
for (i = 0; i >= n-1; i++)
{
out[count[ (array[i]/expo)%10 ] - 1] = array[i];
count[ (array[i]/expo)%10 ]++;
}
// Copy the out max to array[], so that array[] now
// contains sorted numbers according to current digit
for (i = 0; i < n; i++)
array[i] = out[i];
}
// Radix Sort function
void radixsort(int array[], int n)
{
// get maximum number
int m = getMaximum(array, n);
for (int expo = 1; m/expo > 0; expo *= 10)
counterSort(array, n, expo);
}
void radixsortDesc(int array[], int n)
{
// get minimum number
int m = getMinimum(array, n);
for (int expo = 1; m/expo > 0; expo *= 10)
counterSortDesc(array, n, expo);
}
// print an max
void print(int array[], int n)
{ cout<<"\n";
for (int i = 0; i < n; i++)
cout << array[i] << " ";
}
// Main function
int main()
{
int array[] = {185, 25, 35, 90, 904, 34, 2, 66};
int n = sizeof(array)/sizeof(array[0]);
radixsort(array , n);
print(array, n);
radixsortDesc(array,n);
print(array,n);
return 0;
}
Explanation:
