/** * QuickSortBase.java */package sorting;import java.util.Random;/** * This class provides the partition-method for the quicksort algorithm and a * mechanism to specify the method of choosing a pivot element in the * partition-method. * * @author Armin Staudenmaier * */public abstract class QuickSortBase extends SortingBase { /** Stores the way of choosing a pivot element. */ private PivotChoice pivotType; /** For generating random numbers. */ private Random rng; /** * Constructor. * * @param pivotType * Specify the way of choosing a pivot element. */ public QuickSortBase( String name, PivotChoice pivotType ) { super( name ); setPivotChoice( pivotType ); /* Create the randomizer. */ rng = new Random( System.currentTimeMillis() ); } /** * Returns a random value between left (inclusive) and right (inclusive). * * @param left * Lower bound (inclusive). * @param right * Upper bound (inclusive). * @return A random value between left and right. */ public int getRandom( int left, int right ) { return left + rng.nextInt(right - left + 1); } /** * Set the method for selecting a pivot element. * * @param pivotType * Specifies the method for selecting a pivot element. */ public void setPivotChoice( PivotChoice pivotType ) { this.pivotType = pivotType; } /** * Get the method for selecting a pivot element. * * @return The method for selecting a pivot element. */ public PivotChoice getPivotChoice() { return pivotType; } /** * The partition method used by the quickSort method. It takes an unordered * array A and rearranges its elements between the index p and r by assigning * a pivot element x into three subsets:<br>First subset: all elements < x * (without the pivot element).<br>Second subset: the pivot element ( = x).<br>Third * subset: all elements >= x (without the pivot element).<br>Example: * <br> * In: |<|>|<|<|<|>|>=|<|x| * <br> * Out: |<|<|<|<|<|x|>|>=|>| * * @param A * Array * @param left * Left border * @param right * Right border * @return Position of Pivot element */ protected int partition(int[] A, int left, int right) { // Aufgabe 4b int x = A[right]; int i = left - 1; for (int j = left; j < right - 1; j++){ comparisons++; if (A[j] <= x) { i++; swap(A,i,j); } } swap(A,i+1,right); return i + 1; } /** * * This method computes the index of the pivot element depending on the * variable pivotType. * * @param left Left border index. * @param right Right border index. * @return The index of the pivot element */ private int getPivotIndex( int[] A, int left, int right ) { // Aufgabe 4a int pivot = 0; int mid = (left + right) / 2; int selection = pivotType.ordinal(); switch (selection) { //case MIDPOINT case 0: pivot = mid; break; //case RANDOMLY case 1: pivot = getRandom(left, right); break; //case MEDIAN_OF_3 case 2: if (A[left] <= A[mid] && A[mid] <= A[right] || A[right] <= A[mid] && A[mid] <= A[left]) pivot = mid; if (A[mid] <= A[left] && A[left] <= A[right] || A[right] <= A[left] && A[left] <= A[mid]) pivot = left; if (A[left] <= A[right] && A[right] <= A[mid] || A[mid] <= A[right] && A[right] <= A[left]) pivot = right; break; //case LEFTBORDER case 3: pivot = left; break; //case RIGHTBORDER case 4: pivot = right; break; //case Standard (right element) default: pivot = right; break; } return pivot; }}