Cod sursa(job #1155477)

Utilizator adireusadireus adireus Data 26 martie 2014 22:30:27
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

int N, A, B, C;
vector < int >work;

void
readData ()
{
  ifstream in ("radixsort.in");

  in >> N >> A >> B >> C;
  int temp = B;

  work.push_back (B);
  for (int i = 2; i <= N; i++)
    {
      temp = (A * temp + B) % C;
      work.push_back (temp);
    }
}

void
solve ()
{
  vector < int >buckets[256];
  int mask = 0x000000ff;
  for (int i = 0; i <= 3; i++)
    {
      int offset = 8 * i;
      vector < int >::iterator it;
      for (it = work.begin (); it != work.end (); it++)
	{
	  buckets[(*it & mask) >> offset].push_back (*it);
	}

      work.clear ();
      mask = mask << 8;
      for (int i = 0; i <= 255; i++)
	{
	  for (it = buckets[i].begin (); it != buckets[i].end (); it++)
	    {
	      work.push_back (*it);
	    }
	  buckets[i].clear ();
	}
    }
}

void
print ()
{
  ofstream of ("radix.out");
  for (int i = 0; i < N; i = i + 10)
    of << work[i] << ' ';

}

int
main ()
{
  readData ();
  solve ();
  print ();
  return 0;
}