Radix sort (jazyk C++)

Radix Sort je velmi podobný jako Basket sort. Narozdíl od něj je „košíků“ jen deset, označených 0, 1, 2, 3… 8, 9. Třídění se provádí podle číslic v číslech. Nejdřív se roztřídí podle posledních číslic. Košíky se vysypou, a vše se opět roztřídí podle předposledních číslic. Znovu se košíky vysypou… Tohle se dělá tolikrát, kolik číslic má největší číslo. Výsledkem je řada seřazených čísel. Basket sort se hodí pro řazení několika po sobě jdoucích čísel, ale pro velký rozsah mezi nejmenším a největším není moc vhodný.
Radix sort se hodí i na třídění objektů podle většího množství různých parametrů různých typů a různými způsoby. Stačí jen v každém cyklu třídit podle jiné proměnné či pravidla, začít tím nejméně důležitým pravidlem a postupovat až k nejdůležitějšímu. Například pokud chceme z nějakého důvodu třídit auta, nejdřív je rozdělíme podle značky (Škoda, Opel, BMV), pak podle typu (Octavia, Astra), pak podle barvy (červená, zelená, modrá) atd… Možností je nepřeberně, vždy se dá základní princip algoritmu snadno přizpůsobit konkrétné situaci.
V příkladu jsem místo šablony udělal třídu. Důvod je zřejmý – aby tato metoda fungovala i pro čísla s desetinnými místy, muselo by se definovat na kolik míst čísla zpracovávat a poněkud rozšířit příslušná místa kódu. Ale moc složité by to být nemělo. Algoritmus je také v této podobě omezený na unsigned, tedy nezáporná čísla. Sĺo mi jen o to ukázat základní princip, ne dělat super univerzální třídu.

#include <iostream>
#include <sstream>
#include <vector>
#include <iomanip>

#define DIGITS 10 // je jen 10 cislic - 0,1,2,3,4,5,6,7,8,9

using namespace std;

class RadixSort
{
private:

    vector<unsigned int> *data;
    vector<vector<unsigned int> > baskets;
    int maxNumber;

    void returnSortedValuesFromBasketsToData();
    int getDigitAtPozitionX(unsigned int number, int position);
    int howManyDigitsHasMaxNumber();
    void clearBaskets();

public:

    RadixSort(vector<unsigned int> *data);
    ~RadixSort();
    void run();

};

RadixSort::RadixSort(vector<unsigned int> *data)
: data(data)
{
    baskets.resize(DIGITS);
    maxNumber = -1;
}

RadixSort::~RadixSort()
{
}

void RadixSort::returnSortedValuesFromBasketsToData()
{
    vector<unsigned int>::iterator sortedDataValue = data->begin();

    for (vector<vector<unsigned int> >::iterator idx = baskets.begin(); idx != baskets.end(); idx++)
    {
        if (idx->empty())
            continue;

        for (vector<unsigned int>::iterator idy = idx->begin(); idy != idx->end(); idy++)
        {
            *sortedDataValue = *idy;
            sortedDataValue++;
        }
    }
}

int RadixSort::getDigitAtPozitionX(unsigned int number, int position)
{
    ostringstream ss;
    ss << number;
    string snumber = ss.str();

    if (position > snumber.size())
        return 0;

    return (int)(snumber[snumber.size() - position] - '0');
}

int RadixSort::howManyDigitsHasMaxNumber()
{
    ostringstream ss;
    ss << maxNumber;
    string snumber = ss.str();

    return (int)snumber.size();
}

void RadixSort::clearBaskets()
{
    for (vector<vector<unsigned int> >::iterator idx = baskets.begin(); idx != baskets.end(); idx++)
        idx->clear();

}

void RadixSort::run()
{
    /* roztrid cisla v data podle posledni cislice a najdi nejvetsi cislo */
    for (vector<unsigned int>::iterator idx = data->begin(); idx != data->end(); idx++)
    {
        if (maxNumber < *idx)
            maxNumber = *idx;

        int index = getDigitAtPozitionX(*idx, 1);
        baskets.at(index).push_back(*idx);
    }

    returnSortedValuesFromBasketsToData();

    int loopCount = howManyDigitsHasMaxNumber();
    /*
     Nasledujici cyklus se provede tolikrat, kolik mist ma nejvetsi cislo minus
     jedna (pro posledni cislice uz se roztrideni udelalo, soucasti toho bylo
     nalezeni nejvetsi cislice)
     */
    for (int i = loopCount; i > 1; i--)
    {
        clearBaskets();

        for (vector<unsigned int>::iterator idx = data->begin(); idx != data->end(); idx++)
        {
            int index = getDigitAtPozitionX(*idx, i);
            baskets.at(index).push_back(*idx);
        }

        returnSortedValuesFromBasketsToData();
    }
}

void printData(vector<unsigned int> *data)
{
    for (vector<unsigned int>::iterator idx = data->begin(); idx < data->end(); idx++)
        cout << "" << std::setfill('0') << std::setw(2) << *idx;
    cout << endl;
}

int main(int argc, char *argv[])
{
    unsigned int dataSource[] = {55, 3, 8, 48, 3, 7, 6, 11, 5, 29,
        4, 1, 33, 8, 13, 21, 39, 42, 20, 12 };
    vector<unsigned int> data(dataSource,  dataSource + sizeof(dataSource)/sizeof(unsigned int));

    printData(&data);

    RadixSort radix(&data);
    radix.run();

    printData(&data);

    return 0;
}