Cod sursa(job #2126392)

Utilizator TudorVersoiuVersoiu Tudor Sorin TudorVersoiu Data 9 februarie 2018 16:27:23
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include <iostream>
#include <fstream>
#include <queue>

using namespace std;
ifstream f("radixsort.in" );
ofstream g("radixsort.out");

#define BITMASK ((1<<8)-1)

inline int byte(int x, int p) {
    return (x>>(8*(p-1)))&BITMASK;
}

int output[10000003];
void countSort(int v[], int n, int exp)
{
    int bucket[BITMASK+4] = {0};

    // Store count of occurrences in count[]
    for ( int i = 1; i <= n; i++ )
    {
        int grupa = byte(v[i], exp);
        bucket[grupa]++;
    }
    // Change count[i] so that count[i] now contains actual
    // position of this digit in output[]
    for ( int i = 1; i <= BITMASK; i++ )
        bucket[i] += bucket[i - 1];

    // Build the output array
    for ( int i = n; i >= 1; i-- )
    {
        int grupa = byte(v[i], exp);
        output[--bucket[grupa]] = v[i];
    }

    // Copy the output vay to v[], so that v[] now
    // contains sorted numbers according to current digit
    for ( int i = 1; i <= n; i++ )
        v[i] = output[i-1];
}

// The main function to that sorts arr[] of size n using
// Radix Sort

int N, cmax;
int v[10000003];

void GenerateArray() {
    int A, B, C; f >> N >> A >> B >> C;

    v[1] = B;
    for ( int i=2; i<=N; i++ )
        v[i] = (A * v[i-1] + B) % C;
}

void RadixSort(int arr[], int n) {
    for (int cif = 1; cif <=4; cif++ )
        countSort(arr, n, cif);
}
int main()
{
    GenerateArray();
    RadixSort(v, N);

    for ( int i=0; i*10+1<=N; i++ )
        g << v[i*10+1] << ' ';
}