Cod sursa(job #2229361)

Utilizator rnqftwcalina florin daniel rnqftw Data 6 august 2018 16:58:49
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include<bits/stdc++.h>

using namespace std;
#define N_Max 10000007
int v[N_Max];
int vectorAux[N_Max];

void printArray(int array[],int n){

    for(int i = 1 ; i <= n ; i++)
        cout << array[i] << " ";
    cout << endl;
}

void radixSort(int n){
    ofstream out("radixsort.out");
    int mx = -1;
    for(int i = 1 ; i <= n ; i++){
        mx = max(mx,v[i]);
    }
    int significantDigit = 1;
    while(mx/significantDigit > 0){
        int counting[10] = {0};
            for(int i = 1 ; i <= n ; i++)
            counting[v[i]/significantDigit%10]++;

        for(int i = 1 ; i <= 9 ; i++)
            counting[i] += counting[i-1];

        for(int i = n ; i >= 0 ; i -- ){
            vectorAux[counting[v[i]/significantDigit%10]--] = v[i];
        }

        for(int i = 1 ; i <= n ; i ++ )
            v[i] = vectorAux[i];

        significantDigit *= 10;

    }
    for(int i = 1 ; i <= n ; i += 10)
        out << v[i] << " ";

}
int main(){

    int n , a ,b , c;
    ifstream in("radixsort.in");
    in >> n >> a >> b >>c;
    v[1] = b ;
    for(int i = 2 ; i <= n ; i++)
        v[i] = (a * v[i-1] + b) % c;

    radixSort(n);
    for(int i = 1 ; i <= n ; i += 10)
        cout << v[i] << " ";
}