Cod sursa(job #2429207)

Utilizator MortemPlaiasu Iulia-Silvia Mortem Data 8 iunie 2019 14:31:49
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <iostream>
#include <climits>
#include <fstream>

std::ifstream fin("radixsort.in");
std::ofstream fout("radixsort.out");

int * v;
bool has[10000500];
int n,a,b,c;
int byteSize=0xFF;
int byteCount=sizeof(v[0]);

int getByte(int x, int i)
{
  return (x>>(i*8))&byteSize;
}

void countSort(int * arr, int * arr2, int byte )
{
  int countt[byteSize+1]={0};
  for(int i=0;i<n;i++)
  {
    countt[getByte(arr[i],byte)]++;
  }
  for(int i=1;i<=byteSize;i++)
    countt[i]+=countt[i-1];
  for(int i=n-1;i>=0;i--)
  {
    int c= getByte(arr[i],byte);
  //  std::cout<<countt[c]<<"\n";
    arr2[countt[c]-1]=arr[i];
    countt[c]--;
  }
}

void radixSort()
{
  int *temp= new int[n];
  for(int i=0;i<byteCount;i++)
  {
    if(i%2==0)
      countSort(v,temp,0);
    else
      countSort(temp,v,i);
  }
  for(int i=0;i<n;i+=10)
    fout<<v[i]<<" ";
}

int main()
{
  fin>>n>>a>>b>>c;
  v = new int[n];
  v[0]=b;
  for(int i=1;i<n;i++)
    v[i]=(1LL* a * v[i-1] + b) % c;
  radixSort();
}