Java Trace Quicksort. In addition to the trace, submit what the parameters will
ID: 3593966 • Letter: J
Question
Java 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.
Sort the data into ascending order (from smallest to largest).
For each sort, show the array each time it is altered.
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
----------------------
Code from section 18:
/** Sorts an array into ascending order. Uses quick sort with
median-of-three pivot selection for arrays of at least
MIN_SIZE entries, and uses insertion sort for other arrays. */
public static <T extends Comparable<? super T>>
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);
// Sort subarrays Smaller and Larger
quickSort(a, first, pivotIndex - 1);
quickSort(a, pivotIndex + 1, last);
} // end if
} // end quickSort
// Version 4.0
Explanation / Answer
Array Portion: from 0 - 7
26 19 21 12 4 24 9 11
Prtation around: 26 in range portion 0 - 7
Calling sort(arr, 0, 6)
Array Portion: from 0 - 6
11 19 21 12 4 24 9
Prtation around: 11 in range portion 0 - 6
Calling sort(arr, 0, 1)
Array Portion: from 0 - 1
9 4
Prtation around: 9 in range portion 0 - 1
Calling sort(arr, 0, 0)
Array Portion: from 0 - 0
4
Calling sort(arr, 2, 1)
*******After sorting from 0 - 1
4 9
Calling sort(arr, 3, 6)
Array Portion: from 3 - 6
12 19 24 21
Prtation around: 12 in range portion 3 - 6
Calling sort(arr, 3, 2)
Calling sort(arr, 4, 6)
Array Portion: from 4 - 6
19 24 21
Prtation around: 19 in range portion 4 - 6
Calling sort(arr, 4, 3)
Calling sort(arr, 5, 6)
Array Portion: from 5 - 6
24 21
Prtation around: 24 in range portion 5 - 6
Calling sort(arr, 5, 5)
Array Portion: from 5 - 5
21
Calling sort(arr, 7, 6)
*******After sorting from 5 - 6
21 24
*******After sorting from 4 - 6
19 21 24
*******After sorting from 3 - 6
12 19 21 24
*******After sorting from 0 - 6
4 9 11 12 19 21 24
Calling sort(arr, 8, 7)
*******After sorting from 0 - 7
4 9 11 12 19 21 24 26
sorted array
4 9 11 12 19 21 24 26
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.