Cod sursa(job #2550463)

Utilizator Johnny07Savu Ioan-Daniel Johnny07 Data 18 februarie 2020 20:06:43
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;

void radixSort(int *ans, int base, int n)
{
    vector <int>  bucket[base];
    if (n != 0)
    {
        int mod = 1;
        while (true)
        {
            bool next = 0;
            for (int i = 0; i < n; i ++)
            {
                bucket[(ans[i]/mod)%base].push_back(ans[i]);
                if (ans[i]/mod != 0) 
                    next = 1;
            }
            int poz = 0;
            for(int i = 0; i < base; i++)
            {
                int m = bucket[i].size();
                for(int j = 0; j < m; j++)
                {
                    ans[poz] = bucket[i][j]; 
                    poz ++ ;
                }
                bucket[i].clear();
            }
            if (next == 0) break;
            mod *= base;
        }

    }

}

int main()
{
    ifstream f("radixsort.in");
    ofstream g("radixsort.out");

    long long n,a,b,c;
    long long nr;
    

    f >> n >> a >> b >> c;
    int v[n];
    v[0] = b;
    for (int i = 1; i <= n-1;i ++)
    {
        nr = a * v[i- 1] + b;
        nr %= c;
        v[i] = nr;
        
    }
    //cout<<size(v);
    
    radixSort(v, 256, n);

    for (int i = 0; i < n; i+= 10)
    {
        g << v[i] <<" ";
    }

    f.close();
    g.close();


    return 0;
}