Cod sursa(job #2761254)

Utilizator butasebiButa Gabriel-Sebastian butasebi Data 1 iulie 2021 12:34:11
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.17 kb
#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;
}