10

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?

Improve this question
5
  • 2
    How is the pivot selected? You stated two ways it wasn't selected, but not how it was selected. Commented Sep 23, 2014 at 4:19
  • 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. Commented Sep 23, 2014 at 4:21
  • @WinstonEwert Pivot is selected by the first element. Commented Sep 23, 2014 at 4:33
  • @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). Commented Sep 23, 2014 at 5:03
  • 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. Commented Sep 23, 2014 at 11:02

2 Answers 2

Reset to default
9

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.

Improve this answer
6
  • I see, so the standard deviation from the mean really determines the partitioning result. Commented Sep 23, 2014 at 5:39
  • "... 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.) Commented Sep 23, 2014 at 13:20
  • @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. Commented Sep 24, 2014 at 5:18
  • @StephenC: Many 'good' algorithms including quicksort have n^2 worst case complexity. But see edit. Commented Sep 24, 2014 at 5:24
  • @david.pfx - "Some" ... YES. "Almost every" ... NO. Commented Sep 24, 2014 at 14:33
0

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.

Improve this answer

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.