Cod sursa(job #2434979)

Utilizator VladG26Ene Vlad-Mihai VladG26 Data 2 iulie 2019 17:49:49
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <bits/stdc++.h>
#include <fstream>
using namespace std;

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

vector<int> arr, helper;

void countingSort(int digitIndex)
{
  int count[10];
  memset(count, 0, sizeof count);

  for (int num : arr)
  {
    count[(num / digitIndex) % 10]++;
  }
  for (int i = 1; i < 10; i++)
  {
    count[i] += count[i - 1];
  }
  for (int i = arr.size() - 1; i >= 0; i--)
  {
    helper[count[(arr[i] / digitIndex) % 10] - 1] = arr[i];
    count[(arr[i] / digitIndex) % 10]--;
  }

  arr = helper;
}

void radixSort()
{
  int maxElem = *max_element(arr.begin(), arr.end());
  for (int exp = 1; maxElem / exp > 0; exp *= 10)
  {
    countingSort(exp);
  }
}

int main()
{
  int N, A, B, C;
  fin >> N >> A >> B >> C;

  arr.push_back(B%C);

  for (int i = 1; i < N; i++)
  {
    arr.push_back((arr.back() * A + B) % C);
  }
  helper = arr;

  radixSort();
  for (int i = 0; i < N; i +=10)
  {
    fout << arr[i] << " ";
  }
  return 0;
}