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 seperated .h,.cpp, and main.

Answer 1

Hi there, I have tried to implement the above code condition. Let me know if it worked for you.

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include "UniformRandom.h"
using namespace std;


void radixSortA( vector<string> & arr, int stringLen )
{
    const int BUCKETS = 256;

    vector<vector<string>> buckets( BUCKETS );

    for( int pos = stringLen - 1; pos >= 0; --pos )
    {
        for( string & s : arr )
            buckets[ s[ pos ] ].push_back( std::move( s ) );

        int idx = 0;
        for( auto & thisBucket : buckets )
        {
            for( string & s : thisBucket )
                arr[ idx++ ] = std::move( s );

            thisBucket.clear( );
        }
    }
}

void countingRadixSort( vector<string> & arr, int stringLen )
{
    const int BUCKETS = 256;

    int N = arr.size( );
    vector<string> buffer( N );

    vector<string> *in = &arr;
    vector<string> *out = &buffer;

    for( int pos = stringLen - 1; pos >= 0; --pos )
    {
        vector<int> count( BUCKETS + 1 );

        for( int i = 0; i < N; ++i )
            ++count[ (*in)[ i ][ pos ] + 1 ];

        for( int b = 1; b <= BUCKETS; ++b )
            count[ b ] += count[ b - 1 ];

        for( int i = 0; i < N; ++i )
            (*out)[ count[ (*in)[ i ][ pos ] ]++ ] = std::move( (*in)[ i ] );

            // swap in and out roles
        std::swap( in, out );
    }

        // if odd number of passes, in is buffer, out is arr; so copy back
    if( stringLen % 2 == 1 )
        for( int i = 0; i < arr.size( ); ++i )
            (*out)[ i ] = std::move( (*in)[ i ] );
}


void radixSort( vector<string> & arr, int maxLen )
{
    const int BUCKETS = 256;

    vector<vector<string>> wordsByLength( maxLen + 1 );
    vector<vector<string>> buckets( BUCKETS );

    for( string & s : arr )
        wordsByLength[ s.length( ) ].push_back( std::move( s ) );

    int idx = 0;
    for( auto & wordList : wordsByLength )
        for( string & s : wordList )
            arr[ idx++ ] = std::move( s );

    int startingIndex = arr.size( );    
    for( int pos = maxLen - 1; pos >= 0; --pos )
    {
        startingIndex -= wordsByLength[ pos + 1 ].size( );

        for( int i = startingIndex; i < arr.size( ); ++i )
            buckets[ arr[ i ][ pos ] ].push_back( std::move( arr[ i ] ) );

        idx = startingIndex;
        for( auto & thisBucket : buckets )
        {
            for( string & s : thisBucket )
                arr[ idx++ ] = std::move( s );

            thisBucket.clear( );
        }
    }
}

int main( )
{
    vector<string> lst;
    UniformRandom r;

    const int LEN = 5;
    const int ADD = 7;

    for( int i = 0; i < 1000000; ++i )
    {
        string str = "";
        int len = LEN + ADD; //r.nextInt( ADD ); // between 5 and 11 characters

        for( int j = 0; j < len; ++j )
            str += static_cast<char>( 'a' + r.nextInt( 26 ) );

        lst.push_back( str );
    }

    vector<string> arr1 = lst;
    vector<string> arr2 = lst;

    sort( begin( arr1 ), end( arr1 ) );
    radixSortA( arr2, LEN + ADD );

    for( int i = 0; i < arr1.size( ); ++i )
        if( arr1[ i ] != arr2[ i ] )
            cout << "OOPS!!" << endl;
    
    return 0;
}

#########################################

#include <cstdio>
#include <string>
using std::string;

size_t getMax(string arr[], int n){
size_t max = arr[0].size();
for (int i = 1; i < n; i++){
if (arr[i].size()>max)
max = arr[i].size();
}
return max;
}

void countSort(string a[], int size, size_t k){
string *b = NULL; int *c = NULL;
b = new string[size];
c = new int[257];

for (int i = 0; i <257; i++){
c[i] = 0;
//cout << c[i] << "\n";
}
for (int j = 0; j <size; j++){   
c[k < a[j].size() ? (int)(unsigned char)a[j][k] + 1 : 0]++; //a[j] is a string
//cout << c[a[j]] << endl;
}

for (int f = 1; f <257; f++){
c[f] += c[f - 1];
}

for (int r = size - 1; r >= 0; r--){
b[c[k < a[r].size() ? (int)(unsigned char)a[r][k] + 1 : 0] - 1] = a[r];
c[k < a[r].size() ? (int)(unsigned char)a[r][k] + 1 : 0]--;
}

for (int l = 0; l < size; l++){
a[l] = b[l];
}

// avold memory leak
delete[] b;
delete[] c;
}

void radixSort(string b[], int r){
size_t max = getMax(b, r);
for (size_t digit = max; digit > 0; digit--){ // size_t is unsigned, so avoid using digit >= 0, which is always true
countSort(b, r, digit - 1);
}

}

int main(void) {
string data[] = {
"aaaba",
"dfjasdlifjai",
"jiifjeogiejogp",
"aabaaaa",
"gsgj",
"gerph",
"aaaaaaa",
"htjltjlrth",
"joasdjfisdjfdo",
"hthe",
"aaaaaba",
"jrykpjl",
"hkoptjltp",
"aaaaaa",
"lprrjt"
};
puts("before sorting:");
for (size_t i = 0; i < sizeof(data) / sizeof(data[0]); i++) {
printf(" %s\n", data[i].c_str());
}
radixSort(data, (int)(sizeof(data) / sizeof(data[0])));
puts("after sorting:");
for (size_t i = 0; i < sizeof(data) / sizeof(data[0]); i++) {
printf(" %s\n", data[i].c_str());
}
return 0;
}

Thanks for your feedback.