The following partition algorithm is essentially the same as the one (Algorithm
ID: 3575381 • Letter: T
Question
The following partition algorithm is essentially the same as the one (Algorithm 2.7) discussed in the class for moving the pivot (denoted by pivot V below) to its final location in array. Let S[1:7] = {60, 30, 80, 50, 70, 20, 90}. Determine the output line by line from the println statements when S is passed to the algorithm with low = 1 and high = 7. Each line, except the last line, starts with the values of j and i in order, then followed by all elements of S after each swap. Enter your results into the table shown above. How many comparisons will quicksort (Algorithm 2.6) do on a list of W elements that all have the same value? What is the maximum number of times that this partition algorithm will be called by quicksort in the worst case?Explanation / Answer
out put
j=3
i=4
30 50
j=5 and i=6
30 50 60 70
j=6 and i=7
30 50 60 70 80 90
finally
20 30 50 60 70 80 90
povite position=4 th position
worstcase o(n*n)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.