Radix Bucket Search

Я работал над алгоритмом сортировки ведра 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;
}

c++ sorting algorithm radix-sort bucket-sort
person Andrew Hu    schedule 19.03.2015    source источник
comment
Как я могу сделать их просто целыми, даже если они начинаются с 0?   -  person Andrew Hu    schedule 19.03.2015

Ответы (1)


arrow_upward
1
arrow_downward

Перемещая значения из 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]); 
        }
    }
person Jonathan Potter    schedule 19.03.2015