Cod sursa(job #1419565)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 15 aprilie 2015 22:50:18
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.72 kb
#include <stdio.h>

#define MAX_N 10000000
#define BITS 8
#define MASK (1 << BITS) - 1
#define THRESHOLD 64

int v[MAX_N];

void insertionSort(int lo, int hi) {
  for (int i = lo; i < hi; i++) {
    // insereaza v[i] in v[lo..i]
    int x = v[i];
    int j = i;
    while ((j > lo) && (v[j - 1] > x)) {
      v[j] = v[j - 1];
      j--;
    }
    v[j] = x;
  }
}
void radixSort(int lo, int hi, int bits) {
  int ptr[1 << BITS], end[1 << BITS] = {};

  for (int i = lo; i < hi; i++) {
    end[(v[i] >> bits) & MASK]++;
  }
  // deplasement
  ptr[0] = lo;
  end[0] += lo;
  for (int i = 1; i < (1 << BITS); i++) {
    ptr[i] = end[i - 1];
    end[i] += end[i - 1];
  }
  for (int i = 0; i < (1 << BITS); i++) {
    while (ptr[i] != end[i]) {
      int elem = v[ptr[i]];
      int bucket = (elem >> bits) & MASK;
      while (bucket != i) {
        int tmp = v[ptr[bucket]];
        v[ptr[bucket]++] = elem;
        elem = tmp;
        bucket = (elem >> bits) & MASK;
      }
      v[ptr[i]++] = elem;
    }
  }
  if (bits) {
    for (int i = 0; i < (1 << BITS); i++) {
      int size = end[i] - (i ? end[i - 1] : lo);
      if (size > THRESHOLD) {
        radixSort(end[i] - size, end[i], bits - BITS);
      } else if (size > 1) {
        insertionSort(end[i] - size, end[i]);
      }
    }
  }
}
int main(void) {
  FILE *f;
  int n;
  int a, b, c;

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

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

  radixSort(0, n, 24);

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