Consider the QUICKSORT and PARTITION algorithms below and suppose the initial call of QUICKSORT(X, 1,9), is...

Transcribed Image Text:

Consider the QUICKSORT and PARTITION algorithms below and suppose the initial call of QUICKSORT(X, 1,9), is X[1..9] =< 26,54,1,47,95,18,40,1,26 > QUICKSORT(X,p,r) 1 2 3 1 PARTITION(X, p,r) 2 3 if p <r then 4 5 6 7 8 q= PARTITION(X, p,r) QUICKSORT(X, p.q-1) QUICKSORT(X, q + 1,r) v=X[r] i=p-1 for j = p to (r - 1) do if X[j] ≤ v then i=i+1 EXCHANGE(X, i, j) EXCHANGE(X, i+ 1,r) return i + 1 a) What is the value of q returned by the 1" call to PARTITION? b) What are the subarrays of X the instant afterwards the two recursive calls are made to QUICKSORT? c) Draw the whole recursion tree generated from the initial call. (each node should contain the array segment size within it and should be annotated with the non-recursive time outside it) (write the actual values of the input size inside each node) Consider the QUICKSORT and PARTITION algorithms below and suppose the initial call of QUICKSORT(X, 1,9), is X[1..9] =< 26,54,1,47,95,18,40,1,26 > QUICKSORT(X,p,r) 1 2 3 1 PARTITION(X, p,r) 2 3 if p <r then 4 5 6 7 8 q= PARTITION(X, p,r) QUICKSORT(X, p.q-1) QUICKSORT(X, q + 1,r) v=X[r] i=p-1 for j = p to (r - 1) do if X[j] ≤ v then i=i+1 EXCHANGE(X, i, j) EXCHANGE(X, i+ 1,r) return i + 1 a) What is the value of q returned by the 1" call to PARTITION? b) What are the subarrays of X the instant afterwards the two recursive calls are made to QUICKSORT? c) Draw the whole recursion tree generated from the initial call. (each node should contain the array segment size within it and should be annotated with the non-recursive time outside it) (write the actual values of the input size inside each node)

Answer rating: 100% (QA)

Lets go through each part of your question step by step a What is the value of q returned ... View the full answer