Recall the following partition algorithm from quicksort: Partition (A, p, r) x = A[r] i =...

   

Transcribed Image Text:

Recall the following partition algorithm from quicksort: Partition (A, p, r) x = A[r] i = p 1 for jp to r - 1 ( if (A[j] <= x) { i=i+1 swap A[i] and A[j] } } swap A[i+1] and A[r] return i 1 (a) Explain the running time of the algorithm if the initial call is Partition (A, 1. n) (In other words, the input array is A[1,...,n] with size n). (8 pt) (b) Assume that all elements of the input array A has the same value, e.g., A = [1,1,..., 1] with size n. What value does the partition algorithm return? (8 pt) Recall the following partition algorithm from quicksort: Partition (A, p, r) x = A[r] i = p 1 for jp to r - 1 ( if (A[j] <= x) { i=i+1 swap A[i] and A[j] } } swap A[i+1] and A[r] return i 1 (a) Explain the running time of the algorithm if the initial call is Partition (A, 1. n) (In other words, the input array is A[1,...,n] with size n). (8 pt) (b) Assume that all elements of the input array A has the same value, e.g., A = [1,1,..., 1] with size n. What value does the partition algorithm return? (8 pt)

Answer rating: 100% (QA)

a The running time of the partition algorithm in the worstcase scenario is On and in the average and ... View the full answer