8

The quicksort algorithm has an average time complexity of O(n*log(n)) and a worst case complexity of O(n^2).

Assuming some variant of Hoare’s quicksort algorithm, what kinds of input will cause the quicksort algorithm to exhibit worst case complexity?

Please state any assumptions relating to implementation details regarding the specific quicksort algorithm such as pivot selection, etc. or if it's sourced from a commonly available library such as libc.

Some reading:

  1. A Killer Adversary for Quicksort
  2. Quicksort Is Optimal
  3. Engineering a Sort Function
  4. Introspective Sorting and Selection Algorithms
Peter Mortensen
  • 30,738
  • 21
  • 105
  • 131
  • A precondition of the attack outlined in the paper is the ability to run arbitrary executable code, and the best they can come up with is to make quicksort go quadratic? – Anon. Jan 16 '11 at 22:19
  • I propose - if something sounds like homework, it should be answered 1-2 weeks after the question. Although now SO has the answer to pretty much everything so perhaps too late... – nchaud Jan 23 '17 at 18:48

3 Answers3

7

The Quick sort performs worst ie, at O(n^2) when all the values of the pivot chosen is either the largest or smallest of the taken set. Consider this example.

1 2 3 4 5

The pivot chosen say is 1, you will have 4 elements on the right side of the pivot and no elements on the left side. Applying this same logic recursively and the pivot chosen is 2, 3, 4, 5 respectively, we have attained a situation where this sort has performed at its worst possible time.

It has been recommended and proven that Quicksort performs well if the input is shuffled well.

Moreover, selection of a sort usually depends on a clear knowledge about the input domain. For example, if the input is huge, then there is something called as external sort which may use external memory. If the input size is very small, we may go for a merge sort but not for medium and huge input sets since it uses extra memory. The main advantage of Quick sort is its "in-place"ness meaning, no extra memory is being used for the input data. Its worst case time on paper is O(n^2) but still is widely preferred and used. My point here is, sorting algorithms can be changed based on the knowledge on the input set and its a matter of preference.

bragboy
  • 34,892
  • 30
  • 114
  • 171
  • 1
    why shuffle makes it faster? – Alan Coromano Jun 10 '13 at 05:02
  • 1
    @MariusKavansky: Sorting algorithms usually are not fixated. We are talking about applying a strategy for a huge amount of data. If you have an idea about how the input set is going to be, you can efficiently choose sorting methodologies. Quick sort performs poorly on a partially sorted data due to the above said pivot choosing logic. However, if the input set is completely shuffled, the probability of a pivot being chosen ineffective is the least. That is the reason Shuffle makes it faster if not ideal. – bragboy Jun 11 '13 at 10:12
1

To expand on what Bragboy said, instead of only running:

quicksort(array);

Run:

shuffle(array);
quicksort(array);

Where the definition of shuffle() could be:

shuffle(array){
    for(int i = array.length; i > 0; i--){
        r= random number % i;
        swap(array[i], array[r]);
    }
}

Doing so will, likely, deal with the case of getting input which makes quicksort() slow.

David Weiser
  • 5,190
  • 4
  • 28
  • 35
  • Thanks for the info, but the question was about constructing specific types of inputs that would cause quicksort to behave quadratically. –  Jan 16 '11 at 22:24
  • @Joren: how would you improve it? – David Weiser Jan 16 '11 at 22:27
  • @Zenikoder: I know that, I was only illustrating how the shuffle would work. Bragboy's answer is good, I was just adding more detail. – David Weiser Jan 16 '11 at 22:29
  • 2
    By implementing the Fisher-Yates shuffle. Yours has n^n possible code paths, while there are only n! different permutations. Obviously then it can't provide equal probabilities to all the permutations. – Joren Jan 16 '11 at 22:30
  • It's trivial to change `array.length` to `array.length - i` and `array[r]` to `array[r+i]`. – Anon. Jan 16 '11 at 22:32
  • @Joren: Thanks for the suggestion, I changed the shuffle. – David Weiser Jan 16 '11 at 22:40
  • @All. I assume the shuffle has been changes. That looks like the `Fisher-Yates shuffle.` algorithm – Martin York Jan 16 '11 at 23:38
  • why shuffle makes it faster? – Alan Coromano Jun 09 '13 at 16:33
  • 1
    @MariusKavansky: Shuffling the array makes the sort faster because, by shuffling, you can reasonably ensure that you avoid the edge case where quicksort has O(n^2) performance (http://en.wikipedia.org/wiki/Quicksort?#Choice_of_pivot) – David Weiser Jun 10 '13 at 16:54
0

Hoare’s Quicksort algorithm chooses a random pivot. For reproducible results I'd suggest Scowen's modification which, among other things, chooses the middle item from the input. For this variant a sawtooth pattern with the pivot being the smallest appears to be the worst case input:

starting with           {  j   i   h   g   f   a   e   d   c   b  }
compare 1 to 6          { (j)  i   h   g   f  (a)  e   d   c   b  }
compare 6 to 10         {  j   i   h   g   f  (a)  e   d   c  (b) }
compare 6 to 9          {  j   i   h   g   f  (a)  e   d  (c)  b  }
compare 6 to 8          {  j   i   h   g   f  (a)  e  (d)  c   b  }
compare 6 to 7          {  j   i   h   g   f  (a) (e)  d   c   b  }
swap 1<=>6              { (a)  i   h   g   f  (j)  e   d   c   b  }
compare 1 to 5          { (a)  i   h   g  (f)  j   e   d   c   b  }
compare 1 to 4          { (a)  i   h  (g)  f   j   e   d   c   b  }
compare 1 to 3          { (a)  i  (h)  g   f   j   e   d   c   b  }
compare 1 to 2          { (a) (i)  h   g   f   j   e   d   c   b  }
compare 2 to 6          {  a  (i)  h   g   f  (j)  e   d   c   b  }
compare 3 to 6          {  a   i  (h)  g   f  (j)  e   d   c   b  }
compare 4 to 6          {  a   i   h  (g)  f  (j)  e   d   c   b  }
compare 5 to 6          {  a   i   h   g  (f) (j)  e   d   c   b  }
compare and swap 6<=>10 {  a   i   h   g   f  (b)  e   d   c  (j) }
compare 7 to 10         {  a   i   h   g   f   b  (e)  d   c  (j) }
compare 8 to 10         {  a   i   h   g   f   b   e  (d)  c  (j) }
compare 9 to 10         {  a   i   h   g   f   b   e   d  (c) (j) }
compare 2 to 6          {  a  (i)  h   g   f  (b)  e   d   c   j  }
compare 6 to 9          {  a   i   h   g   f  (b)  e   d  (c)  j  }
compare 6 to 8          {  a   i   h   g   f  (b)  e  (d)  c   j  }
compare 6 to 7          {  a   i   h   g   f  (b) (e)  d   c   j  }
swap 2<=>6              {  a  (b)  h   g   f  (i)  e   d   c   j  }
compare 2 to 5          {  a  (b)  h   g  (f)  i   e   d   c   j  }
compare 2 to 4          {  a  (b)  h  (g)  f   i   e   d   c   j  }
compare 2 to 3          {  a  (b) (h)  g   f   i   e   d   c   j  }
compare 3 to 6          {  a   b  (h)  g   f  (i)  e   d   c   j  }
compare 4 to 6          {  a   b   h  (g)  f  (i)  e   d   c   j  }
compare 5 to 6          {  a   b   h   g  (f) (i)  e   d   c   j  }
compare and swap 6<=>9  {  a   b   h   g   f  (c)  e   d  (i)  j  }
compare 7 to 9          {  a   b   h   g   f   c  (e)  d  (i)  j  }
compare 8 to 9          {  a   b   h   g   f   c   e  (d) (i)  j  }
compare 3 to 6          {  a   b  (h)  g   f  (c)  e   d   i   j  }
compare 6 to 8          {  a   b   h   g   f  (c)  e  (d)  i   j  }
compare 6 to 7          {  a   b   h   g   f  (c) (e)  d   i   j  }
swap 3<=>6              {  a   b  (c)  g   f  (h)  e   d   i   j  }
compare 3 to 5          {  a   b  (c)  g  (f)  h   e   d   i   j  }
compare 3 to 4          {  a   b  (c) (g)  f   h   e   d   i   j  }
compare 4 to 6          {  a   b   c  (g)  f  (h)  e   d   i   j  }
compare 5 to 6          {  a   b   c   g  (f) (h)  e   d   i   j  }
compare and swap 6<=>8  {  a   b   c   g   f  (d)  e  (h)  i   j  }
compare 7 to 8          {  a   b   c   g   f   d  (e) (h)  i   j  }
compare 4 to 6          {  a   b   c  (g)  f  (d)  e   h   i   j  }
compare 6 to 7          {  a   b   c   g   f  (d) (e)  h   i   j  }
swap 4<=>6              {  a   b   c  (d)  f  (g)  e   h   i   j  }
compare 4 to 5          {  a   b   c  (d) (f)  g   e   h   i   j  }
compare 5 to 6          {  a   b   c   d  (f) (g)  e   h   i   j  }
compare and swap 6<=>7  {  a   b   c   d   f  (e) (g)  h   i   j  }
compare and swap 5<=>6  {  a   b   c   d  (e) (f)  g   h   i   j  }
Handcraftsman
  • 6,863
  • 2
  • 40
  • 33