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