Question

C++

Implement the radix sort of an array by using a queue for each group. The radix sort is discussed in Section 11.2.3 of Chapter 11 of your textbook. You can get more information in Radix sort.

Answer 1

Below is the solution:

#include <iostream>
#include <queue>
#include <ctime>
#include <cstdlib>
#include <math.h>
using namespace std;

void Sort_Array_Using_Radix(int q[], int n); //function prototype

int main() {
const int SIZE=100; //declare the Max size of the array
int array[SIZE]; //declare the variable array
int seed =time(0); //seed
srand(seed);
for (int i=0;i<SIZE;i++){ //loop SIZE times
      int num=0+rand()%SIZE; //generate the random number
      array[i]=num; //store the random number to arrray
}
for (int j=0;j<SIZE;j++) //loop SIZE times
      cout << array[j] << " "; //print the array value
cout << endl << endl;

Sort_Array_Using_Radix(array, SIZE); //call the function to sort the array using radix

//print the array after sorting
for (int j=0;j<SIZE;j++) //loop SIZE times
      cout << array[j] << " "; //print the array
cout << endl <<endl;
return 0;
}

//implement the function
void Sort_Array_Using_Radix(int q[], int n) {
    queue<int> bins[10]; //one array per possible digit in queue
    int maxDigits=3; //holds amount of digits in largest number
    int currentDigit=0; //starting base for decimal digit
    while (currentDigit < maxDigits) {
        for(int i=0; i<n; i++){ //loop n times
            int divisor = pow(10,currentDigit);
            int num = q[i]; //set to current value of array position
            int digitValue = static_cast<int>((num/divisor)%10); //get the decimal digit at current digit
            bins[digitValue].push(num); //put digits in corresponding bins
        }
        int i=0;
        for(int k=0;k<10;k++){ //loop through all bins
            while (!bins[k].empty()){ //push all elements in bin[k] until empty to a
                int temp=bins[k].front();
                q[i]=temp;
                bins[k].pop();
                i++;
            }
        }
        currentDigit++; //increment
    }
}

sample output:

39 51 37 57 85 80 0 83 0 59 45 41 3 55 4 12 50 27 18 19 56 78 35 69 27 27 15 93 71 9 68 10 61 58 67 98 38 67 82 91 79 27 84 34 82 88 99 84 67 17 56 75 48 43 45 27 22 60 21 93 69 41 4 82 99 23 81 90 43 15 81 74 42 17 8 76 57 7 13 25 77 21 52 25 64 97 4 86 9 25 32 31 67 36 13 18 11 46 8 6 

0 0 3 4 4 4 6 7 8 8 9 9 10 11 12 13 13 15 15 17 17 18 18 19 21 21 22 23 25 25 25 27 27 27 27 27 31 32 34 35 36 37 38 39 41 41 42 43 43 45 45 46 48 50 51 52 55 56 56 57 57 58 59 60 61 64 67 67 67 67 68 69 69 71 74 75 76 77 78 79 80 81 81 82 82 82 83 84 84 85 86 88 90 91 93 93 97 98 99 99