Cod sursa(job #1112534)

Utilizator techLaurentiu Avasiloaie tech Data 19 februarie 2014 20:27:46
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>

using namespace std;

ifstream in ( "radixsort.in" ) ;
ofstream out ( "radixsort.out" ) ;

int n , a , b , c , i ;
unsigned int vect[10000005] ;
int BASE = 10 ; int EXP = 1 ; unsigned int MAX_VALUE; unsigned int temp[10000005] ; int bucket[11] ;

void radix_sort ()
{
    MAX_VALUE = vect[0] ;

    for ( i = 1 ; i < n ; i ++ )
    {
        if ( MAX_VALUE < vect[i] ) { MAX_VALUE = vect[i] ; }
    }

    while ( MAX_VALUE / EXP > 0 ){

    for ( i = 0 ; i < BASE ; i ++ ) { bucket[i] = 0 ; }

    for ( i = 0 ; i < n ; i ++ )
    {
        bucket[(vect[i]/EXP)%BASE] ++ ;
    }

    for ( i = 1 ; i < BASE ; i ++ )
    {
        bucket[i]+=bucket[i-1] ;
    }

    for ( i = n-1 ; i >= 0 ; i -- )
    {
        temp[--bucket[(vect[i]/EXP)%BASE]] = vect[i] ;
    }

    for ( i = 0 ; i < n ; i ++ )
    {
        vect[i] = temp[i] ;
    }

    EXP *= BASE ;

    }
}

int main()
{
    in >> n >> a >> b >> c ;

    vect[0] = b ;

    for ( i = 1 ; i < n ; i ++ )
    {
        vect[i] = ( a * vect[i-1] + b ) % c ;
    }

    radix_sort() ;

    for ( i = 0 ; i < n ; i += 10 )
    {
        out << vect[i] << " " ;
    }

    return 0;
}