Question

The following pseudocode describes the algorithm for a sort of n decimal integers of d digits each: radixNumberSort(theArray: ItemArray, n: integer, d: integer): void for (j = d down to 1) { Initialize 10 groups to empty Initialize a counter for each groups to 0 for (i = 0 through n – 1) { K = jth digit of theArray[i] Place theArray[i] at the end of group k Increase kth counter by 1 } Replace the items in theArray with all the items in group 0, Followed by all the items in group I, and so on. } } a) Convert the above algorithm into a C++ function, using a vector for grouping by digit during the process.

Answer 1

solution;

#include<vector>

#include<cmath>

void radixNumberSort(int *arr, int n,int d){

int i, j, m, p=1, index, temp, count = 0;

vector<int> group[10]={};

for(i=0; i< d; i++){

m = pow(10, i+1);

p = pow(10, i);

for(j=0; j<n; j++){

temp = arr[j]%m;

index = temp/p;

group[index].push_back(arr[j]);

}

count = 0;

for(j=0; j< 10; j++){

while(!group[j].empty()){

arr[count] = *(group[j].begin());

group[j].erase(group[j].begin());

count++;

}

}

}

}