Cod sursa(job #2897359)

Utilizator valentin12Valentin Ion Semen valentin12 Data 3 mai 2022 15:23:47
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream f("radixsort.in");
ofstream g("radixsort.out");

int n, v[100000001], A, B, C;

int getMax(int array[], int n) {
  int maxx = array[0];
  for (int i = 1; i < n; i++)
    if (array[i] > maxx)
      maxx = array[i];
  return maxx;
}

void countingSort(int arr[], int sizee, int place) {
  const int maxx = 10;
  int output[sizee];
  int countt[maxx];

  for (int i = 0; i < maxx; ++i)
    countt[i] = 0;

  for (int i = 0; i < sizee; i++)
    countt[(arr[i] / place) % 10]++;

  for (int i = 1; i < maxx; i++)
    countt[i] += countt[i - 1];

  for (int i = sizee - 1; i >= 0; i--) {
    output[countt[(arr[i] / place) % 10] - 1] = arr[i];
    countt[(arr[i] / place) % 10]--;
  }

  for (int i = 0; i < sizee; i++)
    arr[i] = output[i];
}

void radixsort(int arr[], int sizee) {
  int maxx = getMax(arr, sizee);

  for (int place = 1; maxx / place > 0; place *= 10)
    countingSort(arr, sizee, place);
}

int main()
{
    f >> n;
    f >> A >> B >> C;
    v[0] = B;
    for(int i = 1; i < n; i++)
        v[i] = (A * v[i-1] + B) % C;

    radixsort(v, n);
    for(int i = 0; i < n; i += 10)
        g << v[i] << " ";

    f.close();
    g.close();
    return 0;
}