Cod sursa(job #3175713)

Utilizator andreifilimonPopescu Filimon Andrei Cosmin andreifilimon Data 26 noiembrie 2023 12:53:31
Problema Radix Sort Scor 30
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <stdio.h>
#include <stdlib.h>

#define MAXN 10000000
#define SIGN_BIT 31

int v[MAXN+1];

void swap(int ind1, int ind2)
{
    int aux;
    aux=v[ind1];
    v[ind1]=v[ind2];
    v[ind2]=aux;
}

void sort(int v[], int left, int right, int bitno)
{
    if(left>=right || bitno==-1)
        return;

    int i, j, leftbit;

    leftbit=bitno==SIGN_BIT;

    for(i=left, j=left; i<=right; i++)
    {
        if(((v[i]>>bitno)&1)==leftbit)
        {
            swap(i, j);
            j++;
        }
    }

    sort(v, left, j-1, bitno-1);

    sort(v, j, right, bitno-1);
}

int main()
{
    FILE *fin, *fout;
    fin=fopen("radixsort.in", "r");
    fout=fopen("radixsort.out", "w");
    int n, a, b, c;
    fscanf(fin, "%d%d%d%d", &n, &a, &b, &c);
    int i;
    v[1]=b;
    for(i=2; i<=n; i++)
        v[i]=((long long)a*v[i-1]+b)%c;
    sort(v, 1, n, 31);
    for(i=1; i<=n; i+=10)
        fprintf(fout, "%d ", v[i]);
    fclose(fin);
    fclose(fout);
    return 0;
}