Cod sursa(job #2606301)

Utilizator lev.tempfliTempfli Levente lev.tempfli Data 27 aprilie 2020 14:51:16
Problema Radix Sort Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 1.76 kb


import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) throws IOException {
        File file = new File("radixsort.in");
        Scanner scanner = new Scanner(file);

        ArrayList<Long> v = new ArrayList<>();
        long n, a, b, c;
        n = scanner.nextInt();
        a = scanner.nextInt();
        b = scanner.nextInt();
        c = scanner.nextInt();

        v.add(b % c);
        for (int i = 1; i < n; i++)
            v.add((a * v.get(i - 1) % c + b) % c);

        FileWriter fileWriter = new FileWriter("radixsort.out");
        PrintWriter printWriter = new PrintWriter(fileWriter);

        Radix_Sort.radix_sort(v, 4);

        for (int i = 0; i < n; i += 10)
            printWriter.print(v.get(i) + " ");

        printWriter.close();
        fileWriter.close();
        scanner.close();
    }
}

class Radix_Sort {
    public static void radix_sort(ArrayList<Long> v, final int max_byte_len) {
        final char full_byte = 0xFF;

        ArrayList<Long> helper = new ArrayList<Long>(Collections.nCopies(v.size(), (long) (0)));
        int[] counter = new int[256];

        for (int i = 0; i < max_byte_len; i++) {
            Arrays.fill(counter, 0);
            for (int j = 0; j < v.size(); j++) {
                counter[(int) (v.get(j) >> (i * 8) & full_byte)]++;
            }
            for (int j = 1; j < 256; j++)
                counter[j] += counter[j - 1];
            for (int j = v.size() - 1; j >= 0; j--) {
                helper.set(--counter[(int) (v.get(j) >> (i * 8) & full_byte)], v.get(j));
            }
            ArrayList<Long> temp = v;
            v = helper;
            helper = temp;
        }

    }
}