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

Sorting.java

## 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) {
}

public void sort(int[] array) {
sort(array, 0, array.length);
}
}

/**
*/

/**
* 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) {
}

/*
* 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 {
} 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;
}
}

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