Cod sursa(job #2692828)

Utilizator EdiTNSTanasa Edberg EdiTNS Data 3 ianuarie 2021 21:36:36
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <iostream>
#include <fstream>
#include <vector>
#define MAX_N 10000000

using namespace std;

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

int array[MAX_N];

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

void countSort(int array[], int n , int p)
{
  int victim[n];
  int i, count[10] = {0};
  for( i = 0; i < n; i++)
    count[(array[i]/p) % 10]++;
  for( i = 1; i < 10; i++)
    count[i] += count[i - 1];
    for(i = n - 1; i >= 0; i--)
    {
      victim[count[(array[i]/p)%10] - 1] = array[i];
      count[(array[i]/p)%10]--;
    }
    for(i = 0; i < n; i++)
      array[i] = victim[i];
}

void radixSort(int array[] , int n)
{
  int maxi = getMax(array , n);
  for(int p = 1; maxi/p > 0; p *= 10)
    countSort(array, n, p);
}

void print(int array[] , int n)
{
  for(int i = 0; i < n; i++)
    if(array[i + 1] == array[i]);
    else fout << array[i] << ' ';
}


int main()
{
    int n ,a ,b ,c, victim;
    fin >> n >> a >> b >> c;
    array[0] = b;
    for(int i = 1; i < n; i++)
      array[i] = ((long long)a * array[i - 1] + b) % c;
    radixSort(array , n);
    print(array, n);
    return 0;
}