Radix Bucket Search

Question

I have been working on a Radix bucket sort algorithm, and I've started with 2 digit numbers before working my way up to more digits.

I hard code my loop to run 2 times (since there are 2 digits in the numbers I hardcode) and there is an error I cannot pinpoint in the second loop onwards.

Somewhere in between where I clear my data vector and push values from my buckets to my data vectors something goes awry... any thoughts?

The error only happens with some number inputs... with others like the ones I commented out it works.

#include <math.h>
#include <iostream>
#include <vector>

using namespace std;

// test radix_sort
int main() {
    cout << "==================================\n";
    cout << "Radix bucket sort DEBUG ME\n";
    cout << "==================================\n\n";

    int m = 10;
    int n = 1;

    int arr[] = { 17, 45, 75, 90, 02, 24, 26, 06 }; //create data array
    //int arr[] = { 170, 405, 750, 302, 002, 240, 206, 006 }; //create data array
    vector<int> data (arr, arr + sizeof(arr) / sizeof(arr[0]) ); //create data vector
    int elements = data.size();

    //print data vector
    cout << "Original: ";
    for (int i = 0 ; i < elements ; i++){
    cout << data[i] << " ";
    }
    cout << endl;

    vector< vector<int> > vec(10, vector<int>(0));; //create buckets vector

    for (int t = 0 ; t < 2 ; t++){ //hard coded to run 2 times since max 2 digits

        for (int i = 0 ; i < elements ; i++) //radix sort into buckets
        {
            vec[(data[i]%m)/n].push_back(data[i]);
        }
        data.clear(); //clear from data vector

        for (int i = 0 ; i < elements ; i++) //push buckets in order onto data
        {
            for (int j = 0 ; j < vec[i].size() ; j++)
            {
                data.push_back(vec[i][j]); 
            }
        }

        cout << "#" << t+1 << ": ";
        for (int i = 0 ; i < elements ; i++){ //print data vector
            cout << data[i] << " ";
        }
        cout << endl;


        //multiply modulus by 10
        m = m*10;
        n= n*10;

        for(int i = 0 ; i < 10 ; i++){ //clear all the shit from buckets
            vec[i].clear();
        }
    }
    return 0;
}

Answer 1

Moving the values from vec back to data, you need to iterate through all the 10 buckets, but instead you're only iterating through 8 of them:

   for (int i = 0 ; i < elements ; i++) // elements == 8
   {
        for (int j = 0 ; j < vec[i].size() ; j++)
        {
            data.push_back(vec[i][j]); 
        }
    }

This should be:

   for (int i = 0 ; i < vec.size(); i++) // vec.size() == 10
   {
        for (int j = 0 ; j < vec[i].size() ; j++)
        {
            data.push_back(vec[i][j]); 
        }
    }