4. Suppose you choose the first element as pivot in the list (19, 21,2, 30, 14,

Question

4. Suppose you choose the first element as pivot in the list (19, 21,2, 30, 14, 35, 16, 34, 17). Show changes to 5. Given the following recursive method (15 points) i) Show the changes to stack during the recursion. Assume initial call to foo is with following values a ={12, 13, 15, 23, 12, 27, 10} and 1= 0, and r=a.length-1. ii) What is the method foo trying to accomplish? iii) Write the intial time recurrence, T(N), for foo function. public static int foo (int[] a, int 1, int r)t if (r) return a[l]; int m(l+r) / 2; int u = foo (a, 1, m); int v foo (a, m+1, r); if(u > v) return u else return v;

Explanation / Answer

Quicksort: Quicksort is an algorithm which selects the first element or the last element as the pivot and then compares it will all other elements.

So, here we have an array {19,21,2,30,14,35,16,34,17}

Pivot: 19

Algorithm: Compare 19 with the other elements and if

So, as 19 when compared with 21 will be in right part, and with 2 it will be in left part, so keeping all smaller elements in the same order in the left part and greater in the right part.

We get

{2,14,16,17,19,21,30,35,34}

Out of which the partition 2,14,16 and 17 are considered to be left partition and 21,30,35,34 are considered to be right partition, now the quicksort algorithm will be implemented in these left and right partitions again selecting their first element as the pivot, so on recursive partitions and applying quicksort each time the quicksort algorithm is applied, the pivot element is fixed on its position.

The pivot element is added after the iteration is finisher to a position i+1, where i is the position where the left partition ends.

So, here the position of 19 is fixed after quicksort is applied.

This is the output of the array after first iteration: {2,14,16,17,19,21,30,35,34}.

We are allowed to answer only one question at a time, to get answer to the rest of the questions please post them again.

This is all for the question.

Thank You for using Chegg.!

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.