Cod sursa(job #1346246)

Utilizator CiurezAndreiCiurez Marius-Andrei CiurezAndrei Data 18 februarie 2015 09:13:30
Problema Sortare prin comparare Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <fstream>
using namespace std;
ifstream fin("algsort.in");
ofstream fout("algsort.out");
long long n,a,b,c;
int v[10000002],vmax,i,j,f[256],w[10000002],nr, p ;
int main()
{
    fin>>n;
    for(i=1;i<=n;i++){
        fin>>v[i];
        if(v[i]>vmax)
            vmax=v[i];
    }

    nr = 0;
    while (vmax) {
        nr++;
        vmax = vmax/256;
    }


    p = 0;
    for (;nr--;p+=8) {
        for (i=0;i<=255;i++)
            f[i] = 0;
        for (i=1;i<=n;i++)
            f[ (v[i]>>p)&255 ] ++;

        for (i=1;i<=255;i++)
            f[i] += f[i-1];

        for (i=n;i>=1;i--) {
            w[ f[(v[i]>>p)&255]-- ] = v[i];

        }

        for (i=1;i<=n;i++)
            v[i] = w[i];

    }

    for (i=1;i<=n;i++)
        fout<<v[i]<<" ";


    return 0;
}