Cod sursa(job #1363360)

Utilizator vlad.maneaVlad Manea vlad.manea Data 26 februarie 2015 22:02:46
Problema Radix Sort Scor 30
Compilator java Status done
Runda Arhiva educationala Marime 1.86 kb
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

class RadixSorter {
	public static final int MASK = (1 << 8) - 1;
	
	public static void sort(List<Integer> numbers) {
		for (int bit = 0; bit < 32; bit += 8) {
			int[] counts = new int[1 << 8];
			
			for (int number : numbers) {
				int value = (number >> bit) & MASK;
				++counts[value];
			}
			
			for (int value = 1; value < (1 << 8); ++value) {
				counts[value] += counts[value - 1];
			}
			
			int[] aux = new int[numbers.size()];
			
			for (int i = numbers.size() - 1; i >= 0; --i) {
				int number = numbers.get(i);
				int value = (number >> bit) & MASK;
				aux[--counts[value]] = number;
			}
			
			numbers.clear();
			
			for (int number : aux) {
				numbers.add(number);
			}
		}
	}
}


public class Main {
	public static void main(String[] args) throws IOException {
		InputStream inputStream = new FileInputStream("radixsort.in");
		Scanner scanner = new Scanner(inputStream);

		OutputStream outputStream = new FileOutputStream("radixsort.out");
		PrintWriter writer = new PrintWriter(outputStream);

		int N = scanner.nextInt();
		int A = scanner.nextInt();
		int B = scanner.nextInt();
		int C = scanner.nextInt();
		
		List<Integer> numbers = new ArrayList<>(N);
		numbers.add(B);
		
		for (int i = 1; i < N; ++i) {
			numbers.add((A * numbers.get(i - 1) + B) % C);
		}
		
		RadixSorter.sort(numbers);
		
		for (int i = 0; i < N; i += 10) {
			writer.print(numbers.get(i));
			writer.print(" ");
		}
		
		writer.flush();

		writer.close();
		outputStream.close();

		scanner.close();
		inputStream.close();
	}
}