Sorting.java
Sorting.java — 3.5 KB
Dateiinhalt
import java.util.*; public class Sorting { /** * Implements the QuickSort algorithm. */ private static class Quicksort { private void sort(int[] array, int left, int right) { // Write your implementation here } public void sort(int[] array) { sort(array, 0, array.length); } } /** * Implements the RadixSort algorithm. */ private static class RadixSort { /** * Recursively sorts the input array according to the bit * at index 'bit_idx' starting from the less significant bit. * E.g., if the input is [0010, 0001, 0011] (here for simplicity we * show 4-bit integers) and 'bit_idx' is 1, the array is to be sorted * according to the bit ad index 1 (i.e., the 2nd!), and the output is * [0001, 0010, 0011] (note the bits used to sort). * ^ ^ ^ */ private void sort(int[] array, int left, int right, int bit_idx) { // Write your implementation here } /* * Sorts the input array using MSD RadixSort. */ public void sort(int[] array) { sort(array, 0, array.length, 30); } } // No more tasks below this line. private static boolean checkSolution(int[] array, int[] sorted) { if (array.length != sorted.length) return false; for (int i = 0; i < array.length; ++i) if (array[i] != sorted[i]) return false; return true; } private static <Algorithm> boolean runTest(int[] array, Algorithm algo) { System.out.println("Testing array " + Arrays.toString(array)); int[] copy = new int[array.length]; System.arraycopy(array, 0, copy, 0, copy.length); Arrays.sort(copy); try { ((RadixSort) algo).sort(array); } catch (ClassCastException e) { ((Quicksort) algo).sort(array); } if (!checkSolution(copy, array)) { System.out.println("Fail:\nExpected solution: " + Arrays.toString(copy) + "\nOutput is: " + Arrays.toString(array)); return false; } else { System.out.println("PASS"); return true; } } public static void main(String[] args) { Random rnd = new Random(42); // Quicksort tests Quicksort qs = new Quicksort(); int qsTests = 0, qsPassed = 0; for (int size = 1; size < 21; ++size) { for (int test = 0; test < 5; ++test) { int[] array = new int[size]; for (int i = 0; i < size; ++i) array[i] = rnd.nextInt(101); if (runTest(array, qs)) ++qsPassed; ++qsTests; } } // RadixSort tests RadixSort rs = new RadixSort(); int rsTests = 0, rsPassed = 0; for (int size = 1; size < 21; ++size) { for (int test = 0; test < 5; ++test) { int[] array = new int[size]; for (int i = 0; i < size; ++i) array[i] = rnd.nextInt(101); if (runTest(array, rs)) ++rsPassed; ++rsTests; } } System.out.println("Quicksort: passed " + qsPassed + "/" + qsTests + " tests."); System.out.println("RadixSort: passed " + rsPassed + "/" + rsTests + " tests."); } }