Cod sursa(job #2674928)

Utilizator Teodor94Teodor Plop Teodor94 Data 20 noiembrie 2020 19:30:48
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
// Radix sort with base 256

#include <stdio.h>
#include <vector>
using namespace std;

void swap(int& a, int& b) {
  int aux = a;
  a = b;
  b = aux;
}

#define MAX_N 10000000
#define BASE 256

int v[MAX_N];
vector<int> bucket[BASE];

void sort(int v[], int n, int bitNumber) {
  if (bitNumber == 32)
    return;

  int i, b;
  unsigned int j;
  for (i = 0; i < n; ++i)
    bucket[v[i] >> bitNumber & 255].push_back(v[i]);

  i = 0;
  for (b = 0; b < BASE; ++b) {
    for (j = 0; j < bucket[b].size(); ++j)
      v[i++] = bucket[b][j];
    bucket[b].clear();
  }

  sort(v, n, bitNumber + 8);
}

int main() {
  FILE* fin = fopen("radixsort.in", "r");
  int n, a, b, c, i;
  fscanf(fin, "%d%d%d%d", &n, &a, &b, &c);
  fclose(fin);

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

  sort(v, n, 0);

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