In the quicksort algorithm Assume you have the following sequence of numbers: {1

Question

In the quicksort algorithm

Assume you have the following sequence of numbers:

{19,12,25,17,3}

a- If the last item of the sequence is always choosen as the pivot, provide a permutation of this sequence which would lead to the worst case running time of the quicksort alogorithm?

b-assume you are using the Median of three method to choose your pivot. give an example of an input sequence of five values which would result in the worst case running time for th quicksort algorithm?

and please explain why u will do it in this way

Explanation / Answer

I believe that the worst case for quicksort depends on the choice of the pivot element at every step. Quicksort has its worst performance, if the pivot is likely to be either the smallest, or the largest element in the list (e.g. the first or last element of an already sorted list).

If, e.g. you choose the middle element of the list, an already sorted list does not have the worst case runtime.

So, if you suspect your scenario is likely to a bad case scenario for quicksort, you can simply change your choice of pivot element to make quicksort perform better.

a) . if given sequence will be like: 3, 12, 17, 19, 25 and you always choose last element last element as a pivot,

then it will divide array in two parts where one part will have (n-1) elements and one part will have no element.

So, T(n) = T(n-1) + O(n) , that is O(n^2) - using master theorem

b). When median of three numbers result picking largest number at each step then it will cause worst case, because

again it will divide input array into part where one part will have n-1 elements and other will have no element.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

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