//#define GENERATOR
#define MAX_N 10000000 + 1
#define nume "radixsort"
#ifndef INFOARENA
#define fisier "../algorithm solutions/" nume
//#define fisier nume
#define DBG
#else
#define fisier nume
#endif
#include <algorithm>
#include <cassert>
#include <cstring>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <vector>
#ifdef INFOARENA
#include <tr1/unordered_set>
#include <tr1/unordered_map>
using namespace std::tr1;
#else
#include <unordered_set>
#include <unordered_map>
#endif
using namespace std;
ofstream fout(fisier".out");
//#include <chrono>
//
//#include <ctime>
//#include <cstdlib>
//#include <limits>
//#include <climits>
#ifndef INFOARENA
using namespace std::chrono;
template<class duration_type>
double time_elapsed(const duration_type & d) {
return duration_cast<duration<double>>(d).count();
}
template<class function>
double time_taken(function f) {
auto start = system_clock::now();
f();
auto end = system_clock::now();
return time_elapsed(end - start);
}
#include "../../inputGenerator/inputgenerator.hpp"
void randomints() {
int N = MAX_N - 1;
int MIN_VAL = 0;
int MAX_VAL = 123;
ofstream out(fisier".in");
out<<N<<' ';
// cout << "Generating "<<N<<" numbers in range "<<MIN_VAL<<" "<<MAX_VAL<<": " << endl;
// int *A = new int[N];
out << inputGenerator::randomInt(MIN_VAL, 100) << ' '; //a
out << inputGenerator::randomInt(MIN_VAL, 100) << ' '; //b
out << MAX_VAL << '\n'; //c
// sort(A,A+N,greater<int>());
// for (int i = 0; i < N; ++i)
// out<<A[i]<<' ';
out.close();
}
void generator()
{
// inputGenerator::reSeed();
randomints();
// cout<<time_taken(testRandomInt)<<endl;
}
#endif
int n;
int numbers[MAX_N];
#define get_byte(x) ((x>>byte)&255)
void countsort(int n, int byte, int A[], int B[]) {
int counter[256];
int index[256];
memset(counter, 0, sizeof(counter));
for(int i = 0; i < n; i ++)
++counter[get_byte(A[i])];
index[0] = 0;
for(int i = 1; i < 256; i ++)
index[i] = index[i-1] + counter[i-1];
for(int i = 0; i < n; i ++)
B[index[get_byte(A[i])]++] = A[i];
}
//int B[MAX_N];
void radix(int A[], int n) {
int *B = new int[n]; // avem nevoie de un array ca spatiu de swap
countsort(n, 0, A, B); // sortez dupa primul byte (bitii 1-8)
countsort(n, 8, B, A); // urmatorul byte (bitii 9-16)
countsort(n, 16, A, B); // urmatorul byte (bitii 17-24)
countsort(n, 24, B, A); // urmatorul byte (bitii 25-32)
}
void insertion_sort(int *array, int offset, int end) {
int x, y, temp;
for (x=offset; x<end; ++x) {
for (y=x; y>offset && array[y-1]>array[y]; y--) {
temp = array[y];
array[y] = array[y-1];
array[y-1] = temp;
}
}
}
void radix_sort(int *array, int offset, int end, int shift) {
int x, y, value, temp;
int last[256] = { 0 }, pointer[256];
for (x=offset; x<end; ++x) {
++last[(array[x] >> shift) & 0xFF];
}
last[0] += offset;
pointer[0] = offset;
for (x=1; x<256; ++x) {
pointer[x] = last[x-1];
last[x] += last[x-1];
}
for (x=0; x<256; ++x) {
while (pointer[x] != last[x]) {
value = array[pointer[x]];
y = (value >> shift) & 0xFF;
while (x != y) {
swap(array[pointer[y]], value);
y = (value >> shift) & 0xFF;
}
array[pointer[x]++] = value;
}
}
if (shift > 0) {
shift -= 8;
for (x=0; x<256; ++x) {
temp = x > 0 ? pointer[x] - pointer[x-1] : pointer[0] - offset;
if (temp > 64) {
radix_sort(array, pointer[x] - temp, pointer[x], shift);
} else if (temp > 1) {
// std::sort(array + (pointer[x] - temp), array + pointer[x]);
insertion_sort(array, pointer[x] - temp, pointer[x]);
}
}
}
}
void read()
{
ifstream fin(fisier".in");
int a,b,c;
fin>>n>>a>>b>>c;
assert(0<=n && n<=MAX_N - 1);
numbers[0] = b % c;
for(int i = 1; i < n; i ++)
numbers[i] = (1LL*a*numbers[i-1]%c + b)%c;
}
void write(ofstream& f)
{
for(int i = 0; i < n; i +=10)
f << numbers[i]<< ' ';
f<<endl;
}
void radix1()
{
read();
radix(numbers, n);
write(fout);
}
void radix2()
{
read();
radix_sort(numbers, 0, n, 24);
ofstream fok(fisier".radix2.ok");
write(fok);
}
void stdsort()
{
read();
sort(numbers, numbers + n);
#ifndef INFOARENA
ofstream fok(fisier".ok");
#else
ofstream fok(fisier".out");
#endif
write(fok);
}
void quicksort()
{
read();
qsort(numbers, n, sizeof(int), [](const void *aa, const void *bb){
const int *a = (int *)aa, *b = (int *)bb;
return (*a < *b) ? -1 : (*a > *b);
});
ofstream fok(fisier".ok2");
write(fok);
}
void checker()
{
ifstream out(fisier".out");
ifstream ok(fisier".ok");
int n = MAX_N - 1;
for(int i = 0; i < n; i +=10){
int x, y;
out>>x;
ok>>y;
assert(x == y);
}
}
int main()
{
#ifndef INFOARENA
#ifdef GENERATOR
generator();
#endif
cout<<"radix: "<<time_taken(radix1)<<endl;
// cout<<"radix2: "<<time_taken(radix2)<<endl;
cout<<"standard sort: "<<time_taken(stdsort)<<endl;
// cout<<"quick sort: "<<time_taken(quicksort)<<endl;
checker();
#else
stdsort();
#endif
// radixsort();
return 0;
}