We describe pivoting schemes for quicksort below. Match the pivoting schemes to

Question

We describe pivoting schemes for quicksort below. Match the pivoting schemes to the worst-case complexities. Answer each of question.

1.The median of 5 medians chosen as the pivot, where the median of medians is computed using quick select with randomized pivoting.

2.The median of 5 medians chosen as the pivot, where the median is computed by quick select with median of median pivoting.

3.The smallest element chosen as the pivot

4.The median chosen as the pivot, where the median is computed by the quick select algorithm with randomized pivoting.

5.The average value of the array, i.e, sum of all elements divided by size of array chosen as the pivot.

6.Randomly chosen pivot.

1.The median of 5 medians chosen as the pivot, where the median of medians is computed using quick select with randomized pivoting.

(choose 1 from these)n^2 or n^1.5 or nlog(n) orn or n^3

2.The median of 5 medians chosen as the pivot, where the median is computed by quick select with median of median pivoting.

(choose 1 from these)n^2 or n^1.5 or nlog(n) orn or n^3

3.The smallest element chosen as the pivot

(choose 1 from these)n^2 or n^1.5 or nlog(n) orn or n^3

4.The median chosen as the pivot, where the median is computed by the quick select algorithm with randomized pivoting.

(choose 1 from these)n^2 or n^1.5 or nlog(n) orn or n^3

5.The average value of the array, i.e, sum of all elements divided by size of array chosen as the pivot.

(choose 1 from these)n^2 orn^1.5 or nlog(n) orn or n^3

6.Randomly chosen pivot.

(choose 1 from these)n^2 or n^1.5 or nlog(n) orn or n^3

Explanation / Answer

1. nlog(n)

2. nlog(n)

3.n^2

4. nlog(n)

5.n^2

6. nlog(n)

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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