Cod sursa(job #2195318)

Utilizator ibicecIT Zilla ibicec Data 15 aprilie 2018 23:46:13
Problema Radix Sort Scor 30
Compilator java Status done
Runda Arhiva educationala Marime 1.61 kb
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.PrintWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws FileNotFoundException {
        Scanner scanner = new Scanner(new FileReader("radixsort.in"));
        int n = scanner.nextInt();
        int a = scanner.nextInt();
        int b = scanner.nextInt();
        int c = scanner.nextInt();
        scanner.close();

        int arr[] = new int[n];
        arr[0] = b;
        for (int i=1; i<n; i++) {
            arr[i] = (a * arr[i-1] + b) % c;
        }

        radixSort(arr);

        PrintWriter printWriter = new PrintWriter("radixsort.out");
        for (int i=0; i<n; i+=10) {
            printWriter.printf("%d ", arr[i]);
        }
        printWriter.close();
    }

    static void radixSort(int arr[]) {
        Queue<Integer>[] counter = new LinkedList[256];
        for (int i=0; i<counter.length; i++) {
            counter[i] = new LinkedList<>();
        }

        for (int byteNumber=0; byteNumber<4; byteNumber++) {
            for (int i : arr) {
                int byteValue = getByte(i, byteNumber);
                counter[byteValue].offer(i);
            }
            int k=0;
            for (Queue<Integer> queue : counter) {
                if (queue != null) {
                    while (!queue.isEmpty()) {
                        arr[k++] = queue.poll();
                    }
                }
            }
        }
    }

    static int getByte(int n, int byteNumber) {
        return (n >> (byteNumber * 8)) & 0xFF;
    }
}