Cod sursa(job #2612195)

Utilizator @dinescu.mateiDinescu Matei @dinescu.matei Data 8 mai 2020 16:30:21
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <iostream>
#include <fstream>

using namespace std;

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

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

void countingSort(int array[], int size, int place)
{
  const int max = 10;
  int output[size];
  int count[max];

  for (int i = 0; i < max; ++i)
    count[i] = 0;

  for (int i = 0; i < size; i++)
    count[(array[i] / place) % 10]++;

  for (int i = 1; i < max; i++)
    count[i] += count[i - 1];

  for (int i = size - 1; i >= 0; i--)
  {
    output[count[(array[i] / place) % 10] - 1] = array[i];
    count[(array[i] / place) % 10]--;
  }

  for (int i = 0; i < size; i++)
    array[i] = output[i];
}


void radixsort(int array[], int size)
{

  int max = getMax(array, size);

  for (int place = 1; max / place > 0; place *= 10)
    countingSort(array, size, place);
}

int main()
{

    int n, a, b, c;

    f>>n>>a>>b>>c;

    int v[n];

    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]<<" ";
    return 0;
}