Cod sursa(job #2076365)

Utilizator narcischitescuNarcis Chitescu narcischitescu Data 26 noiembrie 2017 14:43:28
Problema Sortare prin comparare Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <fstream>

using namespace std;

#define MAXSIZE 500001

ifstream f("algsort.in");
ofstream g("algsort.out");

int v[MAXSIZE];
int maxim,n;

void countsort(int x)
{
    int counti[256] = {0};
    int output[MAXSIZE];
    int i;
    for ( i = 1; i <= n ; i++ )
    {
        int aux = (v[i]>>x)&255;
        counti[ aux ]++;
    }

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

    for ( i = n ; i > 0  ; i-- ){
        int aux = (v[i]>>x)&255;
        output[ counti[ aux ]-- ] = v[i];
    }

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

void radix()
{
    int biti = 0;
    while ( maxim )
    {
        countsort(biti);

        biti += 8;

        maxim = maxim >> 8;
    }
}

void read()
{
    f >> n;
    for ( int i = 1; i <= n ; i++ )
    {
        f >> v[i];
        if ( maxim < v[i] )  maxim = v[i];
    }
}

void write()
{
     for ( int i = 1; i <= n ; i++ )
        g << v[i] << " " ;
}
int main()
{
    read();
    radix();
    write();
    return 0;
}