Cod sursa(job #1593676)

Utilizator turbowin120Amarandei-Stanescu Alexandru turbowin120 Data 8 februarie 2016 19:53:12
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.9 kb
#include <iostream>
#include <stdio.h>
using namespace std;
const int BITS = 8;
const int MAXSIZE = 64;
const int MASK = ((1<<8) - 1);
int v[10000010];


void selectsort(int lowest, int highest){
    int k,tmp;

    for(int i=lowest;i<highest;i++){
        k=i;
        for(int j=k+1; j<highest;j++){
            if(v[j]<v[k]) k=j;
        }
        tmp=v[i];
        v[i]=v[k];
        v[k]=tmp;

    }


}

void radixPass( int lowest, int highest, int bits){
    int end[1<<BITS], str[1<<BITS];
    for(int i=0;i< (1<<BITS); i++){
        end[i]=0;
    }

    for(int i = lowest; i < highest; i++)
        end[(v[i]>>bits) & MASK]++;

    str[0]=lowest;
    end[0]+=lowest;

    for(int i=1; i< (1<<BITS);i++){
        str[i] =  end[i-1];
        end[i] += end[i-1];
    }

    for(int i=0;i< (1<<BITS); i++){
        while (str[i]!=end[i]){
            int elem = v[str[i]];
            int bucket = (elem >> bits) & MASK;
            while(bucket != i){
                int tmp = v[str[bucket]];
                v[str[bucket]++]= elem;
                elem = tmp;
                bucket = (elem >> bits) & MASK;

            }
            v[str[i]++]= elem;

        }

    }


    if(bits){
        for(int i=0;i < (1<< BITS); i++){
            int size= end[i] - ( i? end[i-1] : lowest);
            if(size > MAXSIZE)
                radixPass(end[i]-size, end[i], bits-BITS);
            else  if(size>1)
                selectsort(end[i] - size, end[i] );

        }
    }
}


int main()
{
     int nr;
    int N,A,B,C;
    FILE * in;
    in=fopen("radix.in","r");
    fscanf(in,"%d%d%d%d", &N,&A,&B,&C);
    v[0]=B;
    for(int i=1;i<N;i++){
        v[i] = (A * v[i-1] + B) % C;
    }
      radixPass(0, N, 24);
      FILE *out;
      out=fopen("radix.out","w");

  for(int i=1;i<N;i+=10){
    fprintf(out,"%d ", v[i]);
  }
    return 0;
}