Cod sursa(job #2549388)

Utilizator Stefan_RaduStefan Radu Stefan_Radu Data 17 februarie 2020 17:29:31
Problema Radix Sort Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.16 kb
// Stefan

#include <vector>
#include <fstream>
#include <iostream>

using namespace std;

ifstream fin("radixsort.in");
ofstream fout("radixsort.out");

void minSort(vector < int > &v) {
  for (int i = 0; i < (int) v.size(); ++ i) {
    for (int j = i + 1; j < (int) v.size(); ++ j) {
      if (v[i] > v[j]) swap(v[i], v[j]);
    }
  }
}

void bubSort(vector < int > &v) {

  bool sorted = false;
  while (not sorted) {
    sorted = true;
    for (int i = 1; i < (int) v.size(); ++ i) {
      if (v[i] < v[i - 1]) {
        swap(v[i], v[i - 1]);
        sorted = false;
      }
    }
  }
}

void cntSort(vector < int > &v, int maxVal) {

  vector < int > frecv(maxVal + 1);
  for (auto x : v) {
    ++ frecv[x];
  }

  int index = 0;
  for (int i = 0; i <= maxVal; ++ i) {
    for (int j = 1; j <= frecv[i]; ++ j) {
      v[index ++] = i;
    }
  }
}

void radixSort(vector < int > &v) {

  vector < vector < int > > buckets(256);

  for (int buck = 0; buck <= 31; buck += 8) {

    for (auto &x : v) {
      buckets[(x >> buck) & 255].push_back(x);
    }

    int index = 0;
    for (auto &x : buckets) {
      for (auto y : x) {
        v[index ++] = y;
      }
      x.clear();
    }
  }
}

void radixSort2(vector < int > &v) {

  vector < int > frecv(256);

  for (int buck = 0; buck <= 31; buck += 8) {

    for (auto &x : v) frecv[(x >> buck) & 255] += 1;
    for (int i = 1; i <= 255; ++ i) frecv[i] += frecv[i - 1];

    vector < int > aux((int) v.size());
    for (int i = (int) v.size() - 1; i >= 0; -- i) {
      aux[-- frecv[(v[i] >> buck) & 255]] = v[i];
    }

    v = aux;
    fill(frecv.begin(), frecv.end(), 0);
  }
}

int main() {

  /* vector < int > v = {-3, 3, 2, 234, 13, 33, 8475, 784, 258, 18, 25, 2, 1, 29857}; */
  /* vector < int > v = {-1, 13, -19234, -5, -29, 3, 2, 234, 33, 8475, 784, 258, 18, 25, 2, 1, 29857}; */
  /* vector < int > v = {}; */

  int n, a, b, c;
  fin >> n >> a >> b >> c;

  vector < int > v(n);

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

  /* minSort(v); */
  /* bubSort(v); */
  /* cntSort(v, 30000); */
  radixSort2(v);

  for (int i = 0; i < (int) v.size(); i += 10) fout << v[i] << ' ';
  fout << '\n';
}