(C++) The following pseudocode describes the algorithm for a sort of n decimal i

ID: 3727500 • Letter: #

Question

(C++) 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 an algorithm for a sort of n strings of maximum d characters

b) Use C++ Write a function called radixStringSort that sorts its array parameter using your modified sort algorithm.

c) Calculate and print the number of moves, to verify it is in Big-O(n)

d) Write a main() function to test a worst, an averaged and a best cases in terms of time efficiency Reference: https://www.cs.usfca.edu/~galles/visualization/RadixSort.html

Explanation / Answer

a) Convert the above algorithm into an algorithm for a sort of n strings of maximum d characters

radixStringSort(string str_arr[], int r){
for (num = maxlen down to 1 )

count_String_Sort is executed and it checks and calculate
the longest string to sort and replace the array for sorting

b) Use C++ Write a function called radixStringSort that sorts its array parameter using your modified sort algorithm.

size_t getMax(string gM_arr[], int n){

size_t max = gM_arr[0].size();

for (int i = 1; i < n; i++){

if (gM_arr[i].size()>max)

max = gM_arr[i].size();

}

return max;

}

void count_String_Sort(string a1[], int size, size_t k1){

string *b1 = NULL; int *c1 = NULL;

b1 = new string[size];

c1 = new int[257];

for (int i = 0; i <257; i++){

c1[i] = 0;

}

for (int j = 0; j <size; j++){

c1[k1 < a1[j].size() ? (int)a1[j][k1] + 1 : 0]++;

}

for (int f = 1; f <257; f++){

c1[f] += c1[f - 1];

}

for (int r = size - 1; r >= 0; r--){

b1[c1[k1 < a1[r].size() ? (int)a1[r][k1] + 1 : 0] - 1] = a1[r];

c1[k1 < a1[r].size() ? (int)a1[r][k1] + 1 : 0]--;

}

for (int l = 0; l < size; l++){

a1[l] = b1[l];

}

void radixStringSort(string str_arr[], int r){

size_t maxlen = getMax(str_arr, r);

for (size_t num = maxlen; num > 0; num--){

count_String_Sort(str_arr, r, num - 1);

}

Full C++ Program

#include <iostream>

using std::string;

using namespace std;