Quick-sort complexity calculation

1
votes
  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.

2
algorithmtime-complexityquicksort
When I was at University, I looked these things up myself instead of demanding answers from an online community. Have you lost your course text book? - paddy
Yes, so that I'm remembering for this and answer as my opinion and want to cross check here. - dayitv89

2 Answers

2
votes

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.

0
votes

  1. depend on the way you implement quicksort.

  2. depend on the pivot selecting strategy.

  3. depend on the pivot selecting strategy.

  4. right.