Очень простая сортировка по основанию

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

Я сортирую 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, которую можно изменить, изменив цикл фрагмента в системе счисления следующим образом:

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

person Fredrick    schedule 18.02.2011    source источник


Ответы (2)


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

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

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

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

person Sven Marnach    schedule 18.02.2011

Вам также необходимо убедиться, что вы отсортировали каждое ведро от MSD до LSD перед повторной сборкой. Пример: 19,76,90,34,84,12,72,38 Сортировка по 10 сегментам [0-9] в MSD B0=[];B1=[19,12];B2=[];B3=[34 ,38];B4=[];B5=[];B6=[];B7=[76,72];B8=[84];B9=[90]; если бы вы собирали, а затем снова сортировали, это не сработало бы. Вместо этого рекурсивно сортируйте каждое ведро. B1 сортируется в B1B2=[12];B1B9=[19]. После того, как все будет отсортировано, вы сможете собрать правильно.

person cmaynard    schedule 18.02.2011
comment
Я думаю, что форма MSD требует дополнительного рекурсивного шага, а LSD — нет. Пока я рассматриваю пустые цифры как 0 (т.е. 1 = 01), я должен получить строго возрастающий результат. Я не должен видеть что-то вроде 1, 10, 2, 3, 4. Верно? - person Fredrick; 19.02.2011
comment
Если вы добавите ноль, как вы упомянули, все должно работать. - person cmaynard; 22.02.2011