Pagini recente » Cod sursa (job #1428832) | Cod sursa (job #2383087) | Cod sursa (job #1415809) | Cod sursa (job #477570) | Cod sursa (job #1538761)
#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, vector<int>& output, int n, int byte){
int count[1<<8]; //because inside a byte we can store a maximum value of 255
//int output[n];
int temp[1<<8];
memset(count, 0, sizeof(count));
//memset(output, 0, sizeof(output));
for (int i = 0; i < n; ++i){
count[get_byte(arr[i])]++;
}
//decalaj pentru vector
temp[0] = 0;
for (int i = 1;i <= 255; ++i){
temp[i] = temp[i-1] + count[i-1];
// cout<<i<<" ";
}
/*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<<temp[get_byte(arr[i])]<<endl;
//cout<<get_byte(arr[i])<<endl;
output[temp[get_byte(arr[i])]++] = arr[i];
//cout<<i;
}
//for (int i = 0; i <= n-1; i++){
//arr[i] = output[i];
// cout<<arr[i]<<" ";
//}
//cout<<endl<<endl;
}
void radixsort(vector<int>& vec, vector<int>& output, int n){
for (int i = 0; i <= numBytes - 1; ++i){
if (i % 2 == 0)
countingSort(vec, output, n, i);
else
countingSort(output, vec, n, i);
//for (int j = 0;j<=n-1;++j)
// cout<<vec[j]<<" ";
//cout<<endl<<endl;
}
}
void print (vector<int>& vec, int n, ofstream& radixOut){
for(int i = 0; i < n; i +=10)
radixOut << vec[i]<< ' ';
radixOut<<endl;
}
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;
if (c==0) return 0;
if (n==0) return 0;
//cout<<n<<" "<<a<<" "<<b<<" "<<c;
vector<int> vec(n);
vector<int> output(n);
generateVector(vec);
///for (int i = 0; i<=n-1;++i)
//cout<<vec[i]<<" ";
//cout<<endl<<endl;
radixsort(vec,output, n);
//for (int i = 0 ;i<=n-1;i++)
// cout<<vec[i]<<" ";
print(vec,n,radixOut);
return 0;
}