Cod sursa(job #2094803)

Utilizator AkrielAkriel Akriel Data 26 decembrie 2017 16:34:07
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
#include <bits/stdc++.h>

#define formula (components[0] * values[index] + components[1]) % components[2]
#define extractDigit (element / digitSelector) % 10;

using namespace std;

ifstream fin ("radixsort.in");
ofstream fout ("radixsort.out");

const int totalComponents = 3;
const int totalDigits = 10;

vector <int> values, buckets[totalDigits];

int components[totalComponents];

int totalNumbers;

inline void readVariables(){
    fin >> totalNumbers;
    for ( int index = 0; index < totalComponents; index++ )
        fin >> components[index];

    values.push_back(components[1]);
    for ( int index = 0; index < totalNumbers-1; index++ )
        values.push_back(formula);
}

inline void displayAnswer(){
    for ( int element = 0; element < totalNumbers; element += 10 )
        fout << values[element] << " ";
}

inline void radixSort(){
    for ( int digitSelector = 1 ; ; digitSelector *= 10 ){

        for ( auto element : values ){
            int digit = extractDigit;
            buckets[digit].push_back(element);
        }

        int okay = 0;
        for ( int digit = 0; digit < totalDigits; digit++ ){
            if ( buckets[digit].size() ){
                okay ++;
            }
        }

        if (okay < 2)
            break;

        values.clear();
        for ( int digit = 0; digit < totalDigits; digit++ ){
            for ( auto element : buckets[digit] )
                values.push_back(element);
            buckets[digit].clear();
        }

    }
}

int main(){
    readVariables();
    radixSort();
    displayAnswer();
    return 0;
}