Cod sursa(job #2680813)

Utilizator Luca_Miscocilucainfoarena Luca_Miscoci Data 4 decembrie 2020 14:06:12
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <stdio.h>
#include <string.h>
#define NMAX 10000000
#define MAX_BITS 32
#define BITS_PER_STEP 8
#define BASE ( 1 << 8 )
#define MASK (1 << 8) - 1
using namespace std;
int v[NMAX + 3],v1[NMAX + 3] ,f[BASE + 3], ind[BASE + 3];
void mysort (int vec[] , int aux[] ,int n ,int bits){
  int nr;
  if (bits == MAX_BITS)
    return;
  memset (f ,0, sizeof(f));
  for (int i = 0; i < n; i++) {
    nr = vec[i] >> bits & MASK;
    f[nr]++;
  }

  ind[0] = 0;
  for (int i = 1; i < BASE; i++)
    ind[i] = f[i - 1] + ind[i - 1];

  for (int i = 0; i < n; i  ++) {
    nr = vec[i] >> bits & MASK;
    aux[ind[nr]++] = vec[i];
  }
  mysort(aux , vec ,n ,bits + BITS_PER_STEP);
}
int main(){
  FILE *fin ,*fout;
  fin = fopen("radixsort.in","r");
  fout = fopen("radixsort.out","w");
  int a, b, c, n;
  fscanf(fin , "%d%d%d%d" ,&n ,&a ,&b, &c);
  v[0] = b;
  for (int i = 1;i < n; i++){
    v[i] = ((long long) a * v[i - 1] + b) % c;
    printf("%d ",v[i]);
  }
  mysort(v,v1,n,0);
  for(int i = 0; i < n; i += 10)
    fprintf(fout, "%d " ,v[i]);
  return 0;
}