A key procedure in the Quicksort algorithm is to recursively partition the array elements about a pivot element. The attached sheet has a copy of partition() and quicksort().

  

Transcribed Image Text:

1 2 3 4 6 7 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 //quicksort the subarray from a[lo] to a[hi] private static void quicksort (Comparable [] a, int lo, int hi) { if (hi <= lo) return; int j = partition (a, lo, hi); quicksort (a, lo, j-1); quicksort (a, j+1, hi); } // partition the subarray a[lo hi] by returning an indez j // so that allo j-1] <= a[j] <= a[j+1 .. hi] private static int partition (Comparable [] a, int lo, int hi) { int i = lo; int j = hi + 1; Comparable v = a [lo]; while (true) { } //select the pivot // find item on lo to swap while (less (a[++i], v)) = hi) break; // find item on hi to swap while (less (v, a[j])) = = lo) break; // check if pointers croSS if (ij) break; exch(a, i, j); } // put v = alj into position exch(a, lo, j); // with allo j-1] <= a[j] <= a[j+1. hi] return j 1 2 3 4 6 7 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 //quicksort the subarray from a[lo] to a[hi] private static void quicksort (Comparable [] a, int lo, int hi) { if (hi <= lo) return; int j = partition (a, lo, hi); quicksort (a, lo, j-1); quicksort (a, j+1, hi); } // partition the subarray a[lo hi] by returning an indez j // so that allo j-1] <= a[j] <= a[j+1 .. hi] private static int partition (Comparable [] a, int lo, int hi) { int i = lo; int j = hi + 1; Comparable v = a [lo]; while (true) { } //select the pivot // find item on lo to swap while (less (a[++i], v)) = hi) break; // find item on hi to swap while (less (v, a[j])) = = lo) break; // check if pointers croSS if (ij) break; exch(a, i, j); } // put v = alj into position exch(a, lo, j); // with allo j-1] <= a[j] <= a[j+1. hi] return j

Answer rating: 100% (QA)

array 22 34 32 60 55 7 63 10 15 25 Step 1 Choosing the pivot 22 We select the first element 22 as the pivot Pivot 22 The array before partition 22 34 ... View the full answer