What makes for a bad case for quick sort?

Question

I am learning about quicksort and want to illustrate different arrays that quicksort would have a hard time on. The quicksort I have in mind does not have an initial random shuffling, does 2 partition, and does not compute the median.

I thought up of three examples so far:

[1,2,3,4,5,6,7,8,9,10] - when the array is sorted
[10,9,8,7,6,5,4,3,2,1] - when the array is reversed
[1,1,1,1,1,1,1,1,1,1] - when the array is the same values
[1,1,1,2,2,2,3,3,3,3] - when there are few and unique keys

For instance, I'm not too sure about this one:

[1,3,5,7,9,10,8,6,4,2]

So what makes for an array that quicksort has difficulty with compared to one where it is (nearly) ideal?

• Winston Ewert: How is the pivot selected? You stated two ways it wasn't selected, but not how it was selected.
• user40980: Please give Worst case for QuickSort - when can it occur? on StackOverflow a read. I also find sorting.at to be a nice visualization of the sorting algorithms.
• mrQWERTY: @WinstonEwert Pivot is selected by the first element.
• user40980: @Renren29 I've modified the question a bit trying to move it to focus on the reason why quicksort would have difficulty with a given array rather than seeking example arrays (I don't people to be giving you answers of [2,1,2,1,2,1,2,1] and that being the entire answer). The goal of the question would, ideally, be one where other people can come and find out more about the why (which has an answer) rather than examples (of which there are countless).
• MSalters: You're running quicksort down to chunks of 2 elements? Because real-world implementations tend to use simpler sorts for small chunks. E.g. compare-and-swap is a lot simpler than quicksort for N=2.

Answer 1

Every sort algorithm has a worst case, and in many cases the worst case is really bad so it is worth testing for it. The problem is, there is no single worst case just because you know the basic algorithm.

Common worst cases include: already sorted; sorted in reverse; nearly sorted, one out of order element; all values the same; all the same except first (or last) is higher (or lower). We once had a sort where the worst case was a particular sawtooth pattern, which was very hard to predict but quite common in practice.

The worst case for quicksort is one that gets it to always pick the worst possible pivot, so that one of the partitions has only a single element. If the pivot is the first element (bad choice) then already sorted or inverse sorted data is the worst case. For a median-of-three pivot data that is all the same or just the first or last is different does the trick.

---

For quicksort the average complexity is nlogn and worst case is n^2. The reason it's worth triggering worst case behaviour is because this is also the case that produces the greatest depth of recursion. For a naive implementation the recursion depth could be n, which may trigger stack overflow. Testing other extreme situations (including best case) may be worthwhile for similar reasons.

• mrQWERTY: I see, so the standard deviation from the mean really determines the partitioning result.
• Stephen C: "... and in almost every case the worst case is really bad so it is worth testing for it.". That is debatable. When I look at this table: en.wikipedia.org/wiki/… I conclude that for most "good" sort algorithms (i.e. with average O(NlogN) performance or better) the worst and average cases have the same complexity. That suggests that is usually NOT worth testing for the worst case(s). (Given that the test is probably O(N) ... or worse.)
• david.pfx: @Renren29: Median of 3 pivot will be first or last only if 2 or 3 of the values are the same. SD doesn't come into it.
• david.pfx: @StephenC: Many 'good' algorithms including quicksort have n^2 worst case complexity. But see edit.
• Stephen C: @david.pfx - "Some" ... YES. "Almost every" ... NO.

Answer 2

An algorithm escapes from most bad cases using a randomized pivot, excluding continuous elements equals to a pivot from partitioning, and asymmetric search. It searches forward an element greater or equals to a pivot, and searches backward an element less than a pivot.
I thank MichaelT, Asymmetric search is devised to resolve [2,1,2,1,2,1,2,1].

The following result is generated by my function qsort_random(). N = 100,000

usec call compare copy pattern
80132 62946 1971278 877143 random
47326 57578 1606067 215155 sorted : 0,1,2,3,...,n-1
49927 63578 1628883 338715 sorted in reverse : n-1,n-2,...,2,1,0
55619 63781 1596934 377330 nearly reverse : n-2,n-1,n-4,n-3,...,2,3,0,1
54714 66667 1611454 290392 median-3-killer : n-1,0,1,2,...,n-2
1491 1 99999 4 all values the same : n,n,n,...
1577 1 99999 4 first is higher : n,1,1,1,...
2778 2 156159 10 last is lower : n,n,n,...,n,1
2994 3 199996 100009 a few data : n,...,n,1,...,1
3196 3 199996 50012 zigzag : n,1,n,1,...,n,1
917796 56284 67721985 673356 valley(sawtooth?) : n-1,n-3,...,0,...,n-4,n-2

Most cases are faster than a random pattern. Valley pattern is a bad case for most pivot selection.

qsort(3) usec = 14523 call = 0 compare = 884463 copy = 0
qsort_head() usec = 138609 call = 99999 compare = 8120991 copy = 1214397
qsort_middle() usec = 664325 call = 99999 compare = 52928111 copy = 1036047
qsort_trad() usec = 118122 call = 99999 compare = 6476025 copy = 1337523
qsort_random() usec = 295699 call = 58806 compare = 19439952 copy = 732962
qsort_log2() usec = 66411 call = 63987 compare = 1597455 copy = 944821

qsort_log2() escapes from bad case by selecting a pivot in log2(N) elements.
qsort(3) use GNU library which is a merge sort of index sorting.
qsort_trad() select a pivot in first, middle and last elements.
qsort_random() and qsort_log2() don't use swapping.
Source C programs and scripts are posted in github.