Question

Using a queue.

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.

Answer 1

// 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<<"\\";

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;

}

Step-by-step explanation: