Section IV. Sorting and Selection 1) Answer the following questions about QuickS

Question

Section IV. Sorting and Selection 1) Answer the following questions about QuickSort a. What are two worst-case inputs for the version which partitions around the last element in each (sub)array (2 points)? b. Briefly explain why these inputs maximize theruntimee fav 1 ver[A fv' LVE out, atins to- tte-,er+ the worst case? (2 points)? whenearvey con tte p.vot vice c. Under which condition d oes Quicksort achieve (n log n) runtime even in mant d. Name an algorithm that can be used to ensure this condition is met and the (n log n) runtime is achieved e. Explain why this approach is not used in practice despite the theoretical improvement

Explanation / Answer

worst case situation for Quick sort:

1) Array is already sorted in same order.

2) Array is already sorted in reverse order.

3) All elements are same (special case of case 1 and 2)

a)

Example: 1 2 3 4 5 5 6

1 1 1 1 1 1 1

b)

The worst case occurs when the partition process always picks greatest or smallest element as pivot. If we consider above partition strategy where last element is always picked as pivot, the worst case would occur when the array is already sorted in increasing or decreasing order. Following is recurrence for worst case.

I above example : for ex1 - we always pick greatest element as pivot

for ex2 - we always pick 1 as pivot

c)

the problem was easily solved by choosing either a random index for the pivot, choosing the middle index of the partition or (especially for longer partitions) choosing the median of the first, middle and last element of the partition for the pivot. With these modifications, the worst case of Quick sort has less chances to occur, but worst case can still occur if the input array is such that the maximum (or minimum) element is always chosen as pivot.

d)

Randomized Algorithm : picking random element as pivot

e)

Because there is still chance that we alwasy pick largest/sallest (randomly) as pivot

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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