Trace Quicksort.

In addition to the trace, submit what the parameters will be for the next two recursive calls to quickSort.

Use the code given in the else-clause in Section 18.

Do not trace a different version of quicksort.

You only need to show the results after the first partitioning step. In other words, show how the array is changed after the first call to the partition method (displayed in Section 17).

Note that the partition method includes the call to sortFirstMiddleLast.

I recommend writing out the variables to help with your trace (e.g., pivotIndex, pivot, indexFromLeft, etc.).

Dataset:

26, 19, 21, 12, 4, 24, 9, 11

// 12.18 /** * Task: Sorts an array into ascending order. * Uses quick sort with median-of-three pivot selection for arrays of at * least MIN_SIZE elements, and uses insertion sort for other arrays. */ public static > void quickSort(T[] a, int first, int last) { if (last - first + 1 < MIN_SIZE) { insertionSort(a, first, last); } else { // create the partition: Smaller | Pivot | Larger int pivotIndex = partition(a, first, last); arrayPrinter(a, first, last); // sort subarrays Smaller and Larger quickSort(a, first, pivotIndex - 1); quickSort(a, pivotIndex + 1, last); } // end if } // end quickSort

// 12.17 /** * Task: Partitions an array as part of quick sort into two subarrays * called Smaller and Larger that are separated by a single element * called the pivot. * Elements in Smaller are <= pivot and appear before the pivot in * the array. Elements in Larger are >= pivot and appear after the pivot * in the array. * * @param a an array of Comparable objects * @param first the integer index of the first array element; * first >= 0 and < a.length * @param last the integer index of the last array element; * last - first >= 3; last < a.length * @return the index of the pivot */

private static > int partition(T[] a, int first, int last) { int mid = (first + last) / 2; sortFirstMiddleLast(a, first, mid, last); System.out.println("after sort first mid last"); arrayPrinter(a, first, last);

// Assertion: The pivot is a[mid]; a[first] <= pivot and // a[last] >= pivot, so do not compare these two array elements // with pivot.

// move pivot to next-to-last position in array swap(a, mid, last - 1); int pivotIndex = last - 1; System.out.println("after swapping mid and last-1"); arrayPrinter(a, first, last); T pivot = a[pivotIndex];

// determine subarrays Smaller = a[first..endSmaller] and // Larger = a[endSmaller+1..last-1] such that elements in // Smaller are <= pivot and elements in Larger are >= pivot; // initially, these subarrays are empty

int indexFromLeft = first + 1; int indexFromRight = last - 2; boolean done = false; while (!done) { // starting at beginning of array, leave elements that // are < pivot; locate first element that is >= pivot; // you will find one,since last element is >= pivot while (a[indexFromLeft].compareTo(pivot) < 0) indexFromLeft++;

// starting at end of array, leave elements that // are > pivot; locate first element that is <= pivot; // you will find one, since first element is <= pivot while (a[indexFromRight].compareTo(pivot) > 0) indexFromRight--;

assert a[indexFromLeft].compareTo(pivot) >= 0 && a[indexFromRight].compareTo(pivot) <= 0;

if (indexFromLeft < indexFromRight) { swap(a, indexFromLeft, indexFromRight); System.out.println("after swapping the indices"); arrayPrinter(a, first, last); indexFromLeft++; indexFromRight--; } else done = true; } // end while

// place pivot between Smaller and Larger subarrays swap(a, pivotIndex, indexFromLeft); pivotIndex = indexFromLeft;

// Assertion: // Smaller = a[first..pivotIndex-1] // Pivot = a[pivotIndex] // Larger = a[pivotIndex+1..last]

return pivotIndex; } // end partition