Cod sursa(job #2553168)

Utilizator ddeliaioanaaDumitrescu Delia Ioana ddeliaioanaa Data 21 februarie 2020 18:18:25
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <fstream>

using namespace std;


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


void generare(int v[], int n, int A, int B, int C)
{
    int i;
    v[1] = B;
    for(i = 2; i <= n; i ++)
        v[i] = (A * v[i-1] + B) % C;
}

void afisare(int v[], int n)
{
    int i = 1;
    while(i <= n)
    {
       cout<<v[i]<<" ";
        i += 10;
    }

}


void countSort(int v[], int n, int maxi, int exp)
{
    int frecv[10] = {0}, result[n+1], ind = 0, i, j;

    for(i = 1; i <= n ; i ++)
        frecv[ (v[i]/exp)%10 ] += 1;

    for(i = 1; i < 10; i++)
        frecv[i] += frecv[i-1];    //in frecv[i] vom avea pozitia fiecarei cifre in rezultat, poz = cate au fost pana la element + cate sunt ca el


    for(i = n ; i >= 1; i --)
    {
        result[frecv[(v[i]/exp)%10]] = v[i];
        frecv[ (v[i]/exp)%10 ]  --;
    }

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

}


void RadixSort(int v[], int n, int maxi)
{
    int i,copymaxi = maxi,exp = 0, p10;

    while(copymaxi > 0)
    {
        exp += 1;
        copymaxi = copymaxi / 10;

    }
    i = 1;
    p10 = 1;
    while( i <= exp )
    {
        countSort(v,n,maxi,p10);
        p10 = p10 * 10;
        i += 1;
    }


}




int main()
{
    int maxi=0, n, i, A, B, C;
    cin>>n>>A>>B>>C;
    int v[n + 1],result[n + 1];

    generare(v,n,A,B,C);


    for(i = 1; i<=n; i++)
        if(v[i] > maxi)
            maxi = v[i];


    RadixSort(v, n, maxi);

    afisare(v,n);


    return 0;
}