Cod sursa(job #2195315)

Utilizator ibicecIT Zilla ibicec Data 15 aprilie 2018 23:32:18
Problema Radix Sort Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 1.64 kb
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.PrintWriter;
import java.util.LinkedList;
import java.util.List;
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 : arr) {
            printWriter.printf("%d ", 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=0; i<arr.length; i++) {
                int byteValue = getByte(arr[i], byteNumber);
                counter[byteValue].offer(arr[i]);
            }
            int k=0;
            for (Queue<Integer> list : counter) {
                if (list != null) {
                    while (!list.isEmpty()) {
                        arr[k++] = list.poll();
                    }
                }
            }
        }
    }

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