9
$\begingroup$

If you have a quick-sort algorithm, and you always select the smallest (or largest) element as your pivot; am I right in assuming that if you provide an already sorted data set, you will always get worst-case performance regardless of whether your 'already sorted' list is in ascending or descending order?

My thinking is that, if you always choose the smallest element for your pivot, then whether your 'already-sorted' input is sorted by ascending or descending doesn't matter because the subset chosen to be sorted relative to your pivot will always be the same size?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ Your thinking is correct, but you can also argue directly and calculate the running time of quicksort in this case - you'll get $O(n^2)$. $\endgroup$
    – Yuval Filmus
    Aug 31, 2012 at 5:28

3 Answers 3

Reset to default
16
$\begingroup$

The worst case complexity for quicksort is $\Theta(n^2)$. This is achieved by picking pivots that divide the set such that one group has only a single member. With a bad pivot picking algorithm, this can easily be achieved by picking one end of a sorted set. Your assumption is correct.

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ It was better to write it: "... This is achieved by picking pivots that divide the set such that one group has only O(1) member" $\endgroup$
    – user742
    Aug 31, 2012 at 12:51
  • $\begingroup$ @Saeed Amiri: That's right, but it's better to be precise. $\endgroup$
    – MMS
    Aug 31, 2012 at 19:13
  • 1
    $\begingroup$ @SaeedAmiri: O(1) indicates that it is proportional to 1, which means it can be k*1. The actual worst case is achieved when it is exactly 1. I will grant you that O(1) may still lead to O(n^2). $\endgroup$
    – walrii
    Sep 1, 2012 at 0:07
  • $\begingroup$ @MMS, I wrote $O(1)$ to be precise, walrii You wrote:"The worst case complexity for quicksort is $\Theta (n^2)$ ..", but in fact the only way to achieve $\Theta(n^2)$ is not the way you said, yes the way you described is worst case in all, but not the only $\Theta (n^2)$. $\endgroup$
    – user742
    Sep 1, 2012 at 8:53
5
$\begingroup$

Yes! You're thinking is absolutely right! And as correctly mentioned by Yuval Filmus, the running time will be $\Theta(n^2)$

Improve this answer
$\endgroup$
3
$\begingroup$

One subarray will have $0$ or $1$ element while the other will have $(n-1)$ elements; hence it is $O(n^2)$: $$t(n)=t(n-1)+t(0)+O(n)= O(n^2)$$

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.