Cod sursa(job #2694016)

Utilizator SoulSnorterPetre Robert Cristian SoulSnorter Data 7 ianuarie 2021 20:32:20
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.64 kb
#include <iostream>
#include <vector>
#include <stdio.h>

using namespace std;

int getMax(vector<int>& nums, int n)
{
    int mx = nums[0];
    for (int i = 1; i < n; i++)
    {
        if (nums[i] > mx)
            mx = nums[i];
    }

    return mx;
}

void countingSort10(vector<int>& nums, int n, int exp)
{
    int* output = new int[n];
    int arr[10] = { 0 };
    for (int i = 0; i < n; i++)
    {
        arr[(nums[i] / exp) % 10]++;
    }
    for (int i = 1; i < 10; i++)
    {
        arr[i] += arr[i - 1];
    }
    
    for (int i = n - 1; i >= 0; i--)
    {
        output[arr[(nums[i] / exp) % 10] - 1] = nums[i];
        arr[(nums[i] / exp) % 10]--;
    }
    
    for (int i = 0; i < n; i++)
    {
        nums[i] = output[i];
    }
}

void radixSort(vector<int>& nums, int n)
{
    int m = getMax(nums, n);

    for (int exp = 1; m / exp > 0; exp *= 10)
    {
        countingSort10(nums, n, exp);
    }
}

int main()
{
    freopen("radixsort.in", "r", stdin);
    freopen("radixsort.out", "w", stdout);

    int cerinta[4];
    scanf("%d", &cerinta[0]);
    scanf("%d", &cerinta[1]);
    scanf("%d", &cerinta[2]);
    scanf("%d", &cerinta[3]);

    vector<int> nums; //= { 0, 73, 254, 3201, 198, 4780, 5 };
    nums.push_back(cerinta[2]);

    for (int i = 1; i < cerinta[0]; i++)
    {
        int x;
        x = (cerinta[1] * nums[i - 1] + cerinta[2]) % cerinta[3];
        nums.push_back(x);
    }

    /*
    int n = nums.size();
    radixSort(nums, n);
    */
    for (int i = 0; i < nums.size(); i+=10)
    {
        printf("%d ", nums[i]);
    }

    // de refacut
}