Очень простой радикальный вид - PullRequest
Новая
       12

Очень простой радикальный вид

2 голосов
/ 18 февраля 2011

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

Я сортирую 4-байтовые целые числа (без знака для простоты).
Я использую 1 байт в качестве «цифры». Так что у меня 2 ^ 8 = 256 ведер.
Сначала я сортирую самую значимую цифру (MSD).
После каждой сортировки я помещаю их обратно в массив в том порядке, в котором они существуют в контейнерах, а затем выполняю следующую сортировку. В итоге я делаю 4 вида ведер.
Кажется, работает для небольшого набора данных. Так как я делаю это MSD, я предполагаю, что это не стабильно и может потерпеть неудачу с другими данными.

Я что-то пропустил? 

#include <iostream>
#include <vector>
#include <list>

using namespace std;

void radix(vector<unsigned>&);
void print(const vector<list<unsigned> >& listBuckets);
unsigned getMaxForBytes(unsigned bytes);
void merge(vector<unsigned>& data, vector<list<unsigned> >& listBuckets);

int main()
{
    unsigned d[] = {5,3,6,9,2,11,9, 65534, 4,10,17,13, 268435455, 4294967294,4294967293, 268435454,65537};
    vector<unsigned> v(d,d+17);

    radix(v);
    return 0;
}

void radix(vector<unsigned>& data)
{
    int bytes = 1;                                  //  How many bytes to compare at a time
    unsigned numOfBuckets = getMaxForBytes(bytes) + 1;
    cout << "Numbuckets" << numOfBuckets << endl;
    int chunks = sizeof(unsigned) / bytes;

    for(int i = chunks - 1; i >= 0; --i) 
    {
        vector<list<unsigned> > buckets;            // lazy, wasteful allocation
        buckets.resize(numOfBuckets);

        unsigned mask = getMaxForBytes(bytes);
        unsigned shift = i * bytes * 8;
        mask = mask << shift;

        for(unsigned j = 0; j < data.size(); ++j)
        {
            unsigned bucket = data[j] & mask;       //  isolate bits of current chunk
            bucket = bucket >> shift;               //  bring bits down to least significant

            buckets[bucket].push_back(data[j]); 
        }

        print(buckets);

        merge(data,buckets);
    }
}

unsigned getMaxForBytes(unsigned bytes)
{
    unsigned max = 0;
    for(unsigned i = 1; i <= bytes; ++i)
    {
        max = max << 8;
        max |= 0xFF;
    }

    return max;
}

void merge(vector<unsigned>& data, vector<list<unsigned> >& listBuckets)
{
    int index = 0;
    for(unsigned i = 0; i < listBuckets.size(); ++i)
    {
        list<unsigned>& list = listBuckets[i];
        std::list<unsigned>::const_iterator it = list.begin();

        for(; it != list.end(); ++it)
        {
            data[index] = *it;
            ++index;
        }
    }
}

void print(const vector<list<unsigned> >& listBuckets)
{
    cout << "Printing listBuckets: " << endl;
    for(unsigned i = 0; i < listBuckets.size(); ++i)
    {
        const list<unsigned>& list = listBuckets[i];

        if(list.size() == 0) continue;

        std::list<unsigned>::const_iterator it = list.begin();  //  Why do I need std here!?
        for(; it != list.end(); ++it)
        {
            cout << *it << ", ";
        }

        cout << endl;
    }
}



Обновление:
Кажется, хорошо работает в форме LSD, которую можно изменить, изменив цикл chunk в radix следующим образом: 

for(int i = chunks - 1; i >= 0; --i)

Ответы [ 2 ]

3 голосов
/ 18 февраля 2011

Давайте рассмотрим пример с двузначными десятичными числами: 

49, 25, 19, 27, 87, 67, 22, 90, 47, 91

Сортировка по первой цифре дает 

19, 25, 27, 22, 49, 47, 67, 87, 90, 91

Далее вы сортируете по второй цифре, получая 

90, 91, 22, 25, 27, 47, 67, 87, 19, 49

Кажется, неправильно, не так ли? Или это не то, что вы делаете? Может быть, вы можете показать нам код, если я вас неправильно понял.

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

2 голосов
/ 18 февраля 2011

Вы также должны убедиться, что вы сортируете каждый сегмент от MSD до LSD перед повторной сборкой. Пример: 19,76,90,34,84,12,72,38 Сортировка по 10 ведер [0-9] на MSD В0 = []; В1 = [19,12]; В2 = []; В3 = [34,38]; В4 = []; В5 = []; В6 = []; В7 = [76,72]; В8 = [84]; В9 = [90]; если бы вы собирали и затем сортировали снова, это не сработало бы. Вместо этого рекурсивно сортируйте каждое ведро. B1 сортируется по B1B2 = [12]; B1B9 = [19] После того, как все отсортировано, вы можете правильно собрать.

...