Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Wissensmanagement in der Bioinformatik

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.");
    }
}