Radix Sort

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

void printArr ( int arr[], int arrSize )
{
    for ( int i = 0; i < arrSize; i++ ) {
        cout << arr[i] << "   ";
    }
    cout << endl;
}

void radixSort ( int arr[], int arrSize )
{
    const int MaxBuckets = 10;
    //const int MaxBucketSize = 100;
    vector < vector<int> > buckets(MaxBuckets);
    
    //find max value for termination condition
    int maxValue = arr[0];
    for ( int i = 1; i < arrSize; i++ ) {
        if ( arr[i] > maxValue ) {
            maxValue = arr[i];
        }
    }
    
    int radixPos = 0;
    int extractor = pow(10, radixPos);
    while (maxValue / extractor > 0) {
    
        //push the elements to the respective buckets for the radix position
        for ( int i = 0; i < arrSize; i++ ) {
            int bucketIdx = (arr[i] / extractor) % 10;
            buckets[bucketIdx].push_back(arr[i]); 
        }
        
        //put the elements back from the bucket to the array
        int arrIdx = 0;
        for ( int i = 0; i < MaxBuckets; i++ ) {
            for ( int j = 0; j < buckets[i].size(); j++ ) {
                arr[arrIdx++] = buckets[i][j];
            }
        }
        buckets.clear();
        buckets.resize(10);
        cout << "iter "<< radixPos << ": ";
        printArr(arr, arrSize);
        
        radixPos++;
        extractor = pow(10, radixPos);
    }
    
}

int main ( )
{
    cout << "Enter the size: ";
    int arrSize;
    cin >> arrSize;
    
    cout << "Enter the numbers\n";
    int arr[arrSize];
    for ( int i = 0; i < arrSize; i++ ) {
        cin >> arr[i];
    }
    
    radixSort(arr, arrSize);
    
    cout << "--------Array sorted------\n";
    printArr(arr, arrSize);
    
    return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s