Cod sursa(job #2680942)

Utilizator andrei_ciobanuciobanu andrei andrei_ciobanu Data 4 decembrie 2020 17:23:37
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <bits/stdc++.h>


using namespace std;
#define MAXBITS 31
#define NMAX 10000000
int v[NMAX];

void radixsort(int left, int right, int bits_no){
    if (left>=right || bits_no==0) return;
    int i1=left, i2=right;
    while ((v[i1]&(1<<bits_no))==0) i1++;
    while ((v[i2]&(1<<bits_no))>=1) i2--;
    while (i2>i1){
        //printf("swap intre %d si %d, %d, %d\n", v[i1], v[i2], v[i1]&(1<<bits_no), v[i2]&(1<<bits_no));
        swap(v[i1], v[i2]);
        do i1++; while ((v[i1]&(1<<bits_no))==0);
        do i2--; while ((v[i2]&(1<<bits_no))>=1);
    }
    //printf("number=%d\n", 1<<bits_no);
    //for (int j=left; j<=right; j++) printf("%d(%d) ", v[j]&(1<<bits_no), v[j]);
    //printf("\n");
    radixsort(left, i2, bits_no-1);
    radixsort(i2+1, right, bits_no-1);
}

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