Cod sursa(job #1538178)

Utilizator theo.stoicanTheodor Stoican theo.stoican Data 28 noiembrie 2015 16:58:46
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.21 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <limits.h>
#include <cstring>
using namespace std;

#define numBytes sizeof(int)
#define mask 0xFF //this is equivalent with 0000 0000 0000 1111 number 
#define get_byte(n) ((n>>(8*byte))&mask)

int n,a,b,c;

void generateVector(vector<int>& vec){
	vec[0]=b;
	for (int i = 1;i<=n-1;++i){
		vec[i] = (a*vec[i-1]+b)%c;
	}
}
//#define countOccurences( count)
//for (int i = 0; i<=n-1;++i)
//++count[vec[i]]
void countOccurences(vector<int> count, vector<int> vec){
	for (int i = 0;i <= n-1; ++i)
		++count[vec[i]];
}


void countingSort(vector<int>& arr, int n, int byte){
	int count[1<<8]; //because inside a byte we can store a maximum value of 255
	int output[n];
	memset(count, 0, sizeof(count));
	memset(output, 0, sizeof(output));	
	for (int i = 0; i < n; ++i){
		count[get_byte(arr[i])]++;
	}
	for (int i = 1; i<=255; ++i){
		count[i] += count[i-1];
		//cout<<count[i]<<endl;
	}
	/*for (int i = 0; i <= n-1; i++){
	 	//arr[i] = output[i];
	 	cout<<arr[i]<<" ";
	 }
	 cout<<endl<<endl;*/
	for (int i = 0; i<=n-1; ++i){
		//cout<<count[get_byte(arr[i])]<<endl;
		if (count[get_byte(arr[i])]){
			output[count[get_byte(arr[i])]-1]= arr[i];
	//	cout<<count[get_byte(arr[i])]<<" "<<arr[i]<<"       ";
			count[get_byte(arr[i])]--;
		}
	}
	 for (int i = 0; i <= n-1; i++){
	 	arr[i] = output[i];
	 	//cout<<arr[i]<<" ";
	 }
	 //cout<<endl<<endl;
	 
}
void radixsort(vector<int>& vec, int n){
	for (int i = 0; i <= numBytes - 1; ++i){
		countingSort(vec, n, i);
		//for (int i = 0;i<=n-1;++i)
		//	cout<<vec[i]<<" ";
		//cout<<endl<<endl;
	}
}

void print (vector<int>& vec, int n, ofstream& radixOut){
	if (vec[0]<=vec[n-1]){
		for (int i = 0; i<=n-1;i+=10)
			radixOut<<vec[i]<<" ";
	}
	else
	{
		for (int i = n-1; i>=0; i-=10)
			radixOut<<vec[i]<<" ";
	}
}
int main(){
	ifstream radixIn;
	ofstream radixOut;
	//int n, a, b, c;
	radixIn.open("radixsort.in");
	radixOut.open("radixsort.out");
	radixIn>>n;
	radixIn>>a;
	radixIn>>b>>c;
	//cout<<n<<" "<<a<<" "<<b<<" "<<c;
	vector<int> vec(n);
	generateVector(vec);
	//for (int i = 0; i<=n-1;++i)
	//	cout<<vec[i]<<" ";
	//cout<<endl<<endl;
	radixsort(vec, n);
	//for (int i = 0 ;i<=n-1;i++)
	//	cout<<vec[i]<<" ";
	print(vec,n,radixOut);
	return 0;
}