Pagini recente » Cod sursa (job #2882688) | Cod sursa (job #2251659) | Cod sursa (job #2700282) | Cod sursa (job #1743010) | Cod sursa (job #2761254)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define INF INT_MAX
using namespace std;
ifstream f("radixsort.in");
ofstream g("radixsort.out");
struct node
{
int value;
node* next;
};
node** table;
void build_array(int v[], int n, int a, int b, int c)
{
v[1] = b;
for (int i = 2; i <= n; i++)
v[i] = (a * v[i - 1] + b) % c;
}
int find_nr_cif(int v[], int n)
{
int maxx = -INF;
for (int i = 1; i <= n; i ++)
if (v[i] > maxx)maxx = v[i];
int nr_cif = 0;
while (maxx > 0)
{
nr_cif ++;
maxx /= 10;
}
return nr_cif;
}
void hash_insert(node* & head, int x)
{
if (head == NULL)
{
head = new node;
head -> value = x;
head -> next = NULL;
return;
}
node* dummy = head;
while (dummy -> next != NULL)
dummy = dummy-> next;
dummy-> next = new node;
dummy-> next -> value = x;
dummy-> next -> next = NULL;
}
int update_and_del(node* & head)
{
if (head == NULL)return 0;
int aux = head -> value;
node* dummy = head;
head = head -> next;
delete dummy;
return aux;
}
void print(int v[], int n);
void radix_sort(int v[], int n)
{
table = new node * [10];
for (int i = 0; i <= 9; i ++)
table[i] = NULL; //initialization
int nr_cif = find_nr_cif(v, n);
int pow10 = 0;
for (int i = 0; i <= nr_cif; i ++)
{
if (pow10 == 0)pow10 = 1;
else pow10 *= 10;
for (int j = 1; j <= n; j++) {
hash_insert(table[(v[j] / pow10) % 10], v[j]);
}
int poz = 0;
for (int j = 0; j <= 9; j ++)
{
while (table[j] != NULL) {
v[++poz] = update_and_del(table[j]);
}
}
}
}
void print(int v[], int n)
{
for (int i = 1; i <= n; i += 10)
g << v[i] << " ";
g << "\n";
}
int n, a, b, c, v[10000005];
int main()
{
f >> n >> a >> b >> c;
build_array(v, n, a, b, c);
//f >> n;
//for (int i = 1; i <= n; i++)
//f >> v[i];
radix_sort(v, n);
print(v, n);
return 0;
}