Cod sursa(job #2693766)

Utilizator SerbaP123Popescu Serban SerbaP123 Data 6 ianuarie 2021 22:23:38
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <fstream>
#include <vector>
#define nmax (int) 1e7
using namespace std;

ifstream cin("radixsort.in");
ofstream cout("radixsort.out");

int MaxNumbers(int arr[], int nNumbers){
    int Max = arr[0];
    for(int i = 1; i < nNumbers; ++i){
        if(arr[i] > Max){
            Max = arr[i];
        }
    }
    return Max;
}

void CountSort(int arr[], int nNumbers, int exp){
    int sortNumbers[nNumbers], Count[10] = {0};
    for(int i = 0; i < nNumbers; ++i){
        Count[(arr[i] / exp) % 10]++;
    }
    for(int i = 1; i < 10; ++i){
        Count[i] += Count[i - 1];
    }
    for(int i = nNumbers - 1; i >= 0; --i){
        sortNumbers[Count[(arr[i] / exp) % 10] - 1] = arr[i];
        Count[(arr[i] / exp) % 10]--;
    }
    for(int i = 0; i < nNumbers; ++i){
        arr[i] = sortNumbers[i];
    }
}

void RadixSort(int arr[], int nNumbers){
    int Max = MaxNumbers(arr, nNumbers);
    for(int exp = 1; Max / exp > 0; exp *= 10){
        CountSort(arr, nNumbers, exp);
    }
}

int main(){
    int arr[nmax + 5];
    int nNumbers, a, b, c;
    cin >> nNumbers >> a >> b >> c;
    arr[0] = b;
    for(int i = 1; i < nNumbers; ++i){
        arr[i] = (a * arr[i - 1] + b) % c;
    }
    RadixSort(arr, nNumbers);
    for(int i = 0; i < nNumbers; i += 10){
        cout << arr[i] << " ";
    }
    return 0;
}