Cod sursa(job #2125984)

Utilizator razboi4Manole Iulian razboi4 Data 8 februarie 2018 22:31:28
Problema Radix Sort Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 1.91 kb
#include <stdio.h>
#include <stdlib.h>

#define NMAX 10000000

int v[NMAX];

typedef struct Node
{
    int val;

    struct Node *next;
} Node;

int getMax(int v[], int n)
{
    int i;
    int max = 0;

    for (i = 0; i < n; ++ i)
        if (max < v[i])
            max = v[i];

    return max;
}

Node *end(Node *queue)
{
    while (queue->next != NULL)
        queue = queue->next;

    return queue;
}

int is_empty(Node *queue)
{
    if (queue != NULL)
        return 0;

    return 1;
}

int first(Node *queue)
{
    if (queue == NULL)
        return -1;

    return queue->val;
}

void dequeue(Node **queue, int v[], int *cnt)
{
    while (*queue != NULL) {
        Node *temp = *queue;

        v[(*cnt) ++] = (*queue)->val;

        *queue = (*queue)->next;

        free(temp);
    }

    *queue = NULL;
}

void enqueue(Node **queue, int el)
{
    Node *temp = malloc(sizeof(Node));

    temp->val = el;
    temp->next = NULL;

    if (*queue == NULL) {
        *queue = temp;
    }
    else
        (end(*queue))->next = temp;
}

void print(Node *queue)
{
    while (queue != NULL) {
        printf("%d ", queue->val);
        queue = queue->next;
    }

    printf("\n");
}

void countSort(int v[], int n, int e)
{
    Node *Q[10] = {NULL};

    int i;

    for (i = 0; i < n; ++ i)
        enqueue(&Q[(v[i] / e) % 10], v[i]);

    int cnt = 0;

    for (i = 0; i < 10; ++ i)
        dequeue(&Q[i], v, &cnt);
}

void radixSort(int v[], int n)
{
    int M = getMax(v, n);
    int e;

    for (e = 1; M / e > 0; e *= 10)
        countSort(v, n, e);
}

int main()
{
    int A, B, C, N;

    freopen("radixsort.in", "r", stdin);
    freopen("radixsort.out", "w", stdout);
    scanf("%d%d%d%d", &N, &A, &B, &C);

    int i;

    v[0] = B;

    for (i = 0; i < N; ++ i)
        v[i] = (A * v[i - 1] + B) % C;

    radixSort(v, N);

    for (i = 0; i < N; i += 10)
        printf("%d ", v[i + 1]);

    printf("\n");

    return 0;
}