/** * Given a subarray of integers, this method partitions the array using * the following algorithm: * * 1) A pivot element is selected from within the given range * 2) Elements that are greater than the pivot are swapped so that * they have a higher index than the pivot index * 3) Elements that are less than the pivot are swapped so that * they have a lower index than the pivot index * * The final index of the pivot is returned to the caller. * * This method should make some attempt to avoid picking a worst-case * pivot (randomization, median value, etc). * * You may want to swap out-of-order elements two at a time with each * other (rather than one at a time with the pivot) to boost efficiency. * * @param a An array of items to partition * @param min The index of the first element forming the subarray to partition * @param max The index of the last element (exclusive) of the subarray; that * is, the first element NOT under consideration. * * @return int The index of the selected pivot item in its final position * * Precondition: min is greater than or equal to 0, * min is less than max, * max is less than or equal to a.length * Postcondition: All elements with index less than the returned pivot * index have a value less than or equal to the pivot value, * all elements with index greater than the pivot index * have a value greater than or equal to the pivot value. */ public <T extends Comparable<? super T>> int partition(T[] a, int min, int max);