Cod sursa(job #2554760)

Utilizator vlcosminCosmin vlcosmin Data 23 februarie 2020 13:01:24
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include<cstdio>
#include<vector>
#define MAX_BUCKETS 10
#define BASE 10
using namespace std;
 
vector<int>v;
vector<int>g[MAX_BUCKETS];
int nr[MAX_BUCKETS];
int n, a, b, c, maxim;
 
void readArray() {
    FILE* fin = fopen("radixsort.in", "r");
    fscanf(fin,"%d%d%d%d",&n, &a, &b, &c);
    v.push_back(b);
    maxim = b;
    for(int i = 1; i < n; i++) {
        v.push_back((1LL * a * v[v.size() - 1] + b) % c);
        if(v[v.size() - 1] > maxim)
            maxim = v[v.size() - 1];
    }
    fclose(fin);
}
 
void radixSort() {
    vector<int>::iterator it;
    int i, exp, m;
	for (i=0;i<MAX_BUCKETS;++i)
		nr[i] = 0;
    for(exp = 1; maxim / exp > 0; exp *= 10) {
        for(i = 0; i < v.size(); ++i)
		{
			int pos = (v[i] / exp) % BASE;
			//if (g[pos].size() <= nr[pos])
				g[pos].push_back(v[i]);
			//else
				//g[pos][nr[pos]] = v[i];
			++nr[pos];
		}
        m = 0;
        for(i = 0; i < BASE; ++i) {
            for(int j = 0; j= < nr[i]; ++j)
                v[m++] = g[i][j];
        }
        for(i = 0; i <BASE; i++)
            g[i].clear();
    }
}
 
void writeArray() {
    FILE* fout = fopen("radixsort.out", "w");
    for(int i = 0; i < v.size(); i += 10)
        fprintf(fout,"%d ",v[i]);
    fprintf(fout,"\n");
    fclose(fout);
}
 
int main() {
    readArray();
    radixSort();
    writeArray();
    return 0;
}