CODEWITHSUNDEEP
algorithmtime-complexityquicksort
gauravds
gauravds

Reputation: 3011

Quick-sort complexity calculation

  1. What value of q does partition for quick sort return, in case all the elements of the array have same values? myAns: O(n^2)
  2. quick sort algorithm in case array is already sorted as per requirement. myAns: O(n^2)
  3. quick sort algorithm in case array is already sorted in the reverse order of the requirement. myAns: O(n log n)
  4. Suppose partition algorithm used for quick sort portioned the elements into 1-α and α where 0< α ≤1/2, α is constant. Derive the recurrence relation and compute its complexity. myAns: O(n log n)

Please Also answer for:

Discuss Hoare partition algorithm used for portioning the array used in quick sort with suitable example.

Upvotes: 1

Views: 2643

Answers (2)

richselian
richselian

Reputation: 731

  1. depend on the way you implement quicksort.

  2. depend on the pivot selecting strategy.

  3. depend on the pivot selecting strategy.

  4. right.

Upvotes: 0

Zim-Zam O&#39;Pootertoot
Zim-Zam O&#39;Pootertoot

Reputation: 18148

Please specify what your question is in the future.

You need to specify what pivot you're using - I'm guessing that you're always using the first partition element as the pivot in which case your answers for 2 and 3 are correct, but if you were using the middle partition element or a random partition element then your answer for 2 would be incorrect (the expected runtime would be n log n).

Your answer for 4 is incrrect - alpha needs to figure into your complexity analysis. If alpha = .5 then the complexity is n log n, but if alpha = 1/n then the complexity is n^2. You are probably supposed to provide the recurrence relation that you derived as well.

Upvotes: 2

Related Questions