Cod sursa(job #2195249)

Utilizator Narcys01Ciovnicu Narcis Narcys01 Data 15 aprilie 2018 19:44:12
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>


using namespace std;

int a[10000007];
int tmp[10000007];

void count_sort(int n, long long c_s)
{
    int i;
    long long co[10] = {0};

    for (i = 0; i <= n; i++)
        co[(a[i]/c_s)%10]++;

    for (i = 1; i < 10; i++)
        co[i] += co[i - 1]; //

    for (i = n; i >= 0; i--)
    {
        tmp[ co[(a[i]/c_s)%10] - 1] = a[i];
        co[(a[i]/c_s)%10]--;
    }

    for (i = 0; i <= n; i++)
        a[i] = tmp[i];
}

void radixSort(int n)
{
    long long i;
    for (i = 1; i < 1e10-2; i *= 10)
        count_sort(n, i);
}

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

    int n, i, A, B, C;

    fin >> n >> A >> B >> C;
    n--;
    a[0] = B;
    for (i = 1; i <= n; i++)
        a[i] = (A * a[i-1] + B) % C;

    /*
    sort(a, a+n+1);
    for (i = 0; i <= n; i += 10)
        fout << a[i] << " ";
    fout << "\n\n";
    */

    radixSort(n);

    for (i = 0; i <= n; i += 10)
        fout << a[i] << " ";

    fin.close();
    fout.close();
    return 0;
}