Quicksort and Partition Trace Show the operation of Partitio

Quicksort and Partition Trace

Show the operation of Partition (not randomized) on this 1-based array: A = [1, 6, 2, 8, 3, 9, 4, 7, 5], p = 1, q = 9 and the two sub-partitions that result as directed below. In other words, you will trace the three calls to Partition that are highest in the recursion tree. (They are not the first three calls: part a is for the first call) Initially: A = [1, 6, 2, 8, 3, 9, 4, 7, 5], i = 0, j = 1, pivot = A[r] = A[9] = 5 Trace at the conclusion of each pass through the loop lines 3-6 A = [1, 6, 2, 8, 3, 9, 4, 7, 5], i = 1, j = 1, exchanged A[1] with A[1] A = [1, 6, 2, 8, 3, 9, 4, 7, 5], i = 1, j = 2, no exchange A = [1, 6, 2, 8, 3, 9, 4, 7, 5], i = 2, j = 3, exchanged A[2] with A[3] ...you fill in the rest until the loop exists... A = [_, _, _, _, _, _, _, _, _], i =_, j = 4 A = [_, _, _, _, _, _, _, _, _], i =_, j = 5, A = [_, _, _, _, _, _, _, _, _], i =_, j = 6, A = [_, _, _, _, _, _, _, _, _], i =_, j = 7, A = [_, _, _, _, _, _, _, _, _], i =_, j = 8, After the swap in line 7: A = [_, _, _, _, _, _, _, _, _], i =_, j =_, exchanged A[_] with A[_] What does Partition (A, 1, 9) return?___Continuing execution of the top level call to Quickersort, identify the two partitions that will be handled by the recursive calls to Quicksort at this level: On what subarray will Quicksort in line 3 be called? A[_, _] On what subarray will Quicksort in line 4 be called? A[_, _]

Solution

A = [1, 6, 2, 8, 3, 9, 4, 7, 5], i=0, j=1, pivot = A[r] = A[9] = 5

Trace at the conclusion of each pass through the loop lines 3­6

A = [1, 6, 2, 8, 3, 9, 4, 7, 5], i=1, j=1, exchanged A[1] with A[1]

A = [1, 6, 2, 8, 3, 9, 4, 7, 5], i=1, j=2, no exchange

A = [1, 2, 6, 8, 3, 9, 4, 7, 5], i=2, j=3, exchanged A[2] with A[3]

... you fill in the rest until the loop exits ...

A = [1,2,6,8,3,9,4,7,5], i=3, j=4, no exchange

A = [1,2,3,8,6,9,4,7,5],i=3, j=5, exchanged A[3] with A[5]

A = [1,2,3,8,6,9,4,7,5],i=4, j=6, exchanged A[4] with A[5]

A = [1,2,3,4,6,7,8,9,5], i=4, j=7, exchanged A[6] with A[7]

A = [1,2,3,4,5,6,7,9,8], i=5, j=8, exchanged A[5] with A[9] because pivot<arr[j]

After the swap in line 7:

A = [1,2,3,4,5,6,7,8,9], i=8, j=9, exchanged A[8] with A[9]

What does Partition(A, 1, 9) return?

It returns complete sorted array as A=[1,2,3,4,5,6,7,8,9]

Continuing execution of the top level call to Quicksort, identify the two partitions that will be handled by the recursive calls to Quicksort at this level:

(#2) On what subarray will Quicksort in line 3 be called? A[2, 3]

(#3) On what subarray will Quicksort in line 4 be called? A[3,4]