Cod sursa(job #1091399)

Utilizator laurionLaurentiu Ion laurion Data 25 ianuarie 2014 17:40:05
Problema Radix Sort Scor Ascuns
Compilator cpp Status done
Runda Marime 5.43 kb
//#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);
    
    write(fout);
}
void stdsort()
{
    read();
    
    sort(numbers, numbers + n);
    
    ofstream fok(fisier".ok");
    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
    radix1();
#endif
    
//    radixsort();
    
    return 0;
}