Question

Write a C++ program that attempts to make the Radix Sort more practical: make it sort strings of a maximum length of 15. Have an array of strings. Then in the Radix Sort, create an array of LinkedQueue with 95 queues (95 are the printable characters starting with space). Those queues will be used to separate the data then combine them (i.e. bins).

Randomly generate 10,000 strings with lengths from 1 to 15 (during the sort and with strings less than 15, treat all positions at the end that are not there as space). When generating random characters, have only 10% be digits, 10% special characters, and the rest, 80%, alphabetic characters, upper and lowercase.

Before the sort, print out the first 10 strings, print out the middle 10 strings, and print last 10 strings. Then do the radix sort then print out the first 10 strings, print out the middle 10 strings, and print last 10 strings.

For 15 pts extra credit, implement the QuickSort using the randomly generated strings (QuickSort does not have the memory issues of Radix so regular string arrays are fine). Print the first, middle and last 10 strings before AND after the sort.

Please do the programming object-oriented and with separate .h,.cpp, and main files.

Answer 1

// C++ implementation of Radix Sort

#include <iostream>

using namespace std;

// A utility function to get maximum value in arr[]

int getMax(int arr[], int n)

{

    int mx = arr[0];

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

        if (arr[i] > mx)

            mx = arr[i];

    return mx;

}

// A function to do counting sort of arr[] according to

// the digit represented by exp.

void countSort(int arr[], int n, int exp)

{

    int output[n]; // output array

    int i, count[10] = { 0 };

    // Store count of occurrences in count[]

    for (i = 0; i < n; i++)

        count[(arr[i] / exp) % 10]++;

    // Change count[i] so that count[i] now contains actual

    // position of this digit in output[]

    for (i = 1; i < 10; i++)

        count[i] += count[i - 1];

    // Build the output array

    for (i = n - 1; i >= 0; i--) {

        output[count[(arr[i] / exp) % 10] - 1] = arr[i];

        count[(arr[i] / exp) % 10]--;

    }

    // Copy the output array to arr[], so that arr[] now

    // contains sorted numbers according to current digit

    for (i = 0; i < n; i++)

        arr[i] = output[i];

}

// The main function to that sorts arr[] of size n using

// Radix Sort

void radixsort(int arr[], int n)

{

    // Find the maximum number to know number of digits

    int m = getMax(arr, n);

    // Do counting sort for every digit. Note that instead

    // of passing digit number, exp is passed. exp is 10^i

    // where i is current digit number

    for (int exp = 1; m / exp > 0; exp *= 10)

        countSort(arr, n, exp);

}

// A utility function to print an array

void print(int arr[], int n)

{

    for (int i = 0; i < n; i++)

        cout << arr[i] << " ";

}

// Driver Code

int main()

{

    int arr[] = { 170, 45, 75, 90, 802, 24, 2, 66 };

    int n = sizeof(arr) / sizeof(arr[0]);

    

      // Function Call

      radixsort(arr, n);

    print(arr, n);

    return 0;

}