ReqursiveQuickSort.java

/** * RecursiveQuickSort.java */package sorting;import testing.SortingTester;/** * This class provides a sorting method that uses the quicksort algorithm * adapted from "Introduction to Algorithms" by Thomas H. Corman et. al. *  * @author Armin Staudenmaier * */public class RecursiveQuickSort extends QuickSortBase{	/**	 * Constructor	 * 	 * @param pivotType The way of choosing a pivot element.	 */	public RecursiveQuickSort( PivotChoice pivotType ) 	{		super( "RecursiveQuickSort", pivotType );	}	/**	 * Sort the array A by performing quicksort.	 * 	 * @param A The array to be sorted.	 */	public void sort(int[] A) {		quickSort(A, 0, A.length - 1);	}	/**	 * 	 * This Method consists of a divide step: partition	 * and a conquer step: recursive calls to quickSort	 * on the partitioned array.	 * 	 * @param A Array	 * @param left Left border	 * @param right Right border	 */	private void quickSort(int[] A, int left, int right) {		recCalls++;		if (left < right) {			int q = partition(A, left, right);			quickSort(A, left, q - 1);			quickSort(A, q + 1, right);		}	}		public static void main(String[] args) {		// Aufgabe 5		SortingTester aufg5 = new SortingTester();		SortingBase qsort = new RecursiveQuickSort(PivotChoice.RIGHTBORDER);		int[] array_aufg5 = {10, 3, 6, 9, 12, 34, 7, 1, 18, 25, 30, 13, 4, 17, 15, 23, 21};				// Aufgabe 5d		qsort.resetCounters();		qsort.sort(array_aufg5);		qsort.printArray(array_aufg5);		System.out.println("Rekursive Aufrufe: " + qsort.getNumberOfRecursionCalls() + "\nComparisons: " + qsort.getComparisons());				// Aufgabe 5e		int[] array200 = aufg5.getRandomArray(200);		int[] array500 = aufg5.getRandomArray(500);		int[] array1000 = aufg5.getRandomArray(1000);		int[] array10000 = aufg5.getRandomArray(10000);				qsort.sort(array200);		qsort.sort(array500);		qsort.sort(array1000);		qsort.sort(array10000);				System.out.println(aufg5.testCorrectness(qsort) + "\n");		System.out.println(aufg5.testPerformance(qsort, 200, 1000) + "\n");		System.out.println(aufg5.testPerformance(qsort, 500, 1000) + "\n");		System.out.println(aufg5.testPerformance(qsort, 1000, 1000) + "\n");		System.out.println(aufg5.testPerformance(qsort, 10000, 1000) + "\n");				System.out.println("Array[200] sortiert?: " + qsort.isSorted(array200));		System.out.println("Array[500] sortiert?: " + qsort.isSorted(array500));		System.out.println("Array[1000] sortiert?: " + qsort.isSorted(array1000));		System.out.println("Array[10000] sortiert?: " + qsort.isSorted(array10000));	}}