Cod sursa(job #2592429)

Utilizator RG1999one shot RG1999 Data 1 aprilie 2020 18:08:10
Problema Radix Sort Scor 0
Compilator c-32 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void sort_count(int *v, int n, int shft) {

    int vl;
    int frq = 0;
    int* sorted = malloc(n * sizeof(int));
    int* app = calloc(300, sizeof(int));
    for(int i = 0; i < n; i++) {
        vl  =  v[i] << shft >> 24;
        app[vl]++;
        frq = vl > frq ? vl : frq; 
    }

    for(int i = 0; i <= frq; i++) {
        app[i] += app[i - 1];
    }

    for(int i = 0; i < n; i++) {
        vl  =  v[i] << shft >> 24;
        sorted[app[vl] - 1]  = v[i];
        app[vl]--;
    }

    memcpy(v, sorted, n * sizeof(int));
    free(sorted);
    free(app);

    

}

int main() {
    int n, a, b, c;
    scanf("%d %d %d %d", &n, &a, &b, &c);
    int* v = malloc(n * sizeof(int));
    v[0] = b;
    for(int i = 1; i < n; i++) {
        v[i] = (a * v[i - 1] + b) % c;
    }
    sort_count(v, n, 24);
    sort_count(v, n, 0);
    sort_count(v, n, 8);
    sort_count(v, n, 16);
    for(int i = n - 1; i >= 0; i--) {
        if((n - i - 1) % 10 == 0) {
            printf("%d ", v[i]);
        }
    }
    free(v);
    

}