Cod sursa(job #1433744)

Utilizator k_ounu_eddyIacob Eduard k_ounu_eddy Data 9 mai 2015 19:02:23
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.1 kb
#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <stdio.h>
#include <cstring>
#define TOTAL_BYTES sizeof(v[0])
#define NMAX 10000000
using namespace std;

int v[NMAX];

void genereazaNumere(int N, int A, int B, int C, int &max)
{
   v[0] = B;
   max = v[0];
   for(int i=1;i<N;i++){
       v[i] = (1LL * A * v[i-1] + B) % C;
       if(max<v[i])
       {
           max = v[i];
       }
   }
}

void printVector(int N)
{
    ofstream fout("radixsort.out");
    for(int i = 0; i < N; i +=10)
    {
        fout << v[i]<< ' ';
    }
    fout<<endl;
    fout.close();
}

void printFirstNNumbers(int n)
{
    for(int i=0;i<n;i++)
        cout<<i<<" ";
    cout<<endl;
}

void countSort(int A[], int B[], int N, int byteNumber, int max)
{
    int counter[255];
    memset(counter, 0, 255 * sizeof(int));

    #ifdef debug
    cout<<"A=";
    printVector(A, N);
    cout<<endl;
    /*   	cout<<"  ";
    printFirstNNumbers(max);
    _getch();*/
    #endif

    for(int i=0;i<N;i++)
    {
    counter[(A[i]>>(8*byteNumber)) & 0xff] += 1;

    #ifdef debug
    cout<<"c=";
    printVector(counter, max);
    cout<<" A["<<i<<"]:"<<A[i]<<endl;	
    #endif
    }

    for(int i=1;i<255;i++){
        counter[i] = counter[i-1] + counter[i];
    }

    #ifdef debug
    cout<<"c=";
    printVector(counter, 255);	
    #endif
    for(int i=N-1;i>=0;i--)
    {	
    /*while(aux<counter[i])
        {
        B[aux] = i;
        aux++;
    }*/
    B[counter[A[i]>>(8*byteNumber) & 0xff]-1] = A[i];
    counter[A[i]>>(8*byteNumber) & 0xff]--;
    }

    #ifdef debug
    cout<<"Dupa prima sortare:"<<endl;
    printVector(B, N);
    cout<<endl;
    _getch();
    #endif
}

void radixSort(int N, int max)
{
    int *temp = new int[N];
    countSort(v, temp, N, 0, max);
    countSort(temp, v, N, 1, max);	
    countSort(v, temp, N, 2, max);	
    countSort(temp, v, N, 3, max);	
    delete[] temp;
    printVector(N);	
}

int main()
{
    long long N,A,B,C;

    fstream fin("radixsort.in");

    int max = -1;
    fin>>N>>A>>B>>C;
    genereazaNumere(N,A,B,C,max);
    max++;
    radixSort(N, max);

    fin.close();

    return 0;
}