Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
2  
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)$. –  Yuval Filmus Aug 31 '12 at 5:28
add comment

3 Answers

up vote 13 down vote accepted

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.

share|improve this answer
2  
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" –  user742 Aug 31 '12 at 12:51
    
@Saeed Amiri: That's right, but it's better to be precise. –  MMS Aug 31 '12 at 19:13
1  
@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). –  walrii Sep 1 '12 at 0:07
    
@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)$. –  user742 Sep 1 '12 at 8:53
add comment

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

share|improve this answer
add comment

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)$$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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