Cod sursa(job #2676787)

Utilizator YusyBossFares Yusuf YusyBoss Data 24 noiembrie 2020 23:46:06
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <iostream>
#include <stdio.h>
#define NMAX 10000000
#define MAX_BITS 32
#define BITS_PAIR 8
#define MAXPAIRNR (1 << 8)
#define MASK (1 << 8) - 1

using namespace std;

int n;
int v[NMAX + 1], cv[NMAX + 1], f[MAXPAIRNR + 1], ind[MAXPAIRNR + 1];

void set_vector(int a, int b, int c) {
  int i;

  v[0] = b;
  for (i = 1; i < n; i++)
    v[i] = ((long long) a * v[i - 1] + b) % c;
}

void resetf() {
  int i;
  for (i = 0; i <= MAXPAIRNR; i++)
    f[i] = 0;
}

void mysort(int bits) {
  int i, max1, nr;

  if (bits == MAX_BITS)
    return;

  resetf();

  max1 = 0;
  for (i = 0; i < n; i++) {
    cv[i] = v[i];

    nr = v[i] >> bits & MASK;
    f[nr]++;

    if (nr > max1)
      max1 = nr;
  }

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

  for (i = 0; i < n; i++) {
    nr = cv[i] >> bits & MASK;
    v[ind[nr]] = cv[i];
    ind[nr]++;
  }

  mysort(bits + BITS_PAIR);
}

int main() {
  FILE *fin, *fout;
  int a, b, c, i;

   fin = fopen ("radixsort.in", "r");
  fscanf(fin, "%d%d%d%d", &n, &a, &b, &c);
  fclose( fin );

  set_vector(a, b, c);
  mysort(0);

  fout = fopen("radixsort.out", "w");
  for (i = 0; i < n; i += 10)
    fprintf(fout, "%d ", v[i]);
  fclose( fout );
  return 0;
}