Cod sursa(job #1189895)

Utilizator lvamanuLoredana Vamanu lvamanu Data 23 mai 2014 20:39:18
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

#define MAXN 10000002 
#define TOTAL_BYTES 4
#define RADIX_SIZE 8

int N;
int V[MAXN];
int count[10];

int getByteMy(int x, int i) {
    return (x >> (i * 8)) & (0xFF);
   
}

void countSort(int V[], int res[], int poz) {
    int count[ 1 << RADIX_SIZE];
    memset(count, 0, sizeof (count));
    for (int i = 0; i < N; i++) {
        int val = getByteMy(V[i], poz);
        count[val]++;
    }
    int index[1 << RADIX_SIZE];
    memset(index, 0, sizeof (index));
    // cum sum 
    index[0] = count[0];
    for (int i = 1; i < 1 << RADIX_SIZE; i++) {
        index[i] = index[i - 1] + count[i];
    }

    for (int i = N - 1; i >= 0; i--) {
        int byte = getByteMy(V[i], poz);
        index[byte]--;
        res[index[byte]] = V[i];
        
    }
}

void radixSort() {
    int* temp = new int[N];
    for (int i = 0; i < TOTAL_BYTES; i++) {
        if (i % 2 == 0) {
            countSort(V, temp, i);
        } else {
            countSort(temp, V, i);
        }
    }
}

int main() {
    freopen("radixsort.in", "r", stdin);
    freopen("radixsort.out", "w", stdout);
    int A, B, C;
    cin >> N >> A >> B >> C;
    V[0] = B;
    for (int i = 1; i < N; i++) {
        V[i] = (A * V[i - 1] + B) % C;
    }
    // cout << getByteMy(2, 0) << " "; 
    // cout << getByteMy(V[1], 0) << " ";
    //    cout << getByte(511, 0); 
    radixSort();
    for (int i = 0; i < N; i = i + 10) {
        cout << V[i] << " ";
    }
    cout << endl;

    fclose(stdin);
    fclose(stdout);
    return 0;
}