Radix Bucket Search

Question

Я работаю над алгоритмом сортировки ковша Radix, и я начал с двухзначных чисел, прежде чем прокладывать свой путь до большего количества цифр.

Я жестко программирую свою петлю для запуска 2 раза (так как есть 2 цифры в цифрах, которые я кодирую), и есть ошибка, которую я не могу определить во втором цикле и далее.

Где-то между тем, где я очищаю свой вектор данных и выталкиваю значения из своих ведер в свои векторы данных, что-то идет наперекосяк ... любые мысли?

Ошибка происходит только с некоторыми вводами количества ... с другими, такими как те, которые я прокомментировал, это работает.

#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

Перемещение значения из vec обратно data, вам нужно перебрать все 10 ведер, но вместо этого вы итерацию только через 8 из них:

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

Это должно быть:

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]); 
     } 
    }