Cod sursa(job #2549336)

Utilizator Stefan_RaduStefan Radu Stefan_Radu Data 17 februarie 2020 16:57:17
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.7 kb
// Stefan

#include <vector>
#include <fstream>

using namespace std;

ifstream cin("radixsort.in");
ofstream cout("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 < 4; ++ buck) {

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

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

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;
  cin >> n >> a >> b >> c;

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

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

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