complexity of quick sort algorithm

Question

The standard worst case complexity of quick sort is O(n^2). What is this worst case and how can I make modifications in such a case to come up with a better behaviour? This is just a theoretical question.

Somebody answered this here: See http://stackoverflow.com/questions/4019528/quick-sort-worst-case — Mikhail, Dec 02 '12 at 00:08

score 1 · Accepted Answer · answered Dec 02 '12 at 09:02

1

The worst case is whenever you choose a pivot, it always turns out to be either the largest or the smallest element in the segment that you're sorting. To improve on the worst case, you need to have a good method of choosing the pivot.

answered Dec 02 '12 at 09:02

NPE

486,780
108
951
1,012

score 0 · Answer 2 · answered Dec 02 '12 at 00:10

0

Worst case is when the data is already sorted.

A way to compensate is to randomly choose the first pivot.

answered Dec 02 '12 at 00:10

Mikhail

7,749
11
62
136

The worst case is contingent: see other answers. – user207421 Dec 02 '12 at 23:01

score 0 · Answer 3 · answered Dec 02 '12 at 08:53

0

The worst case depends on what partitioning method you are using. In the simplest case the worst case is when the data is already sorted. That's why you don't use it.

answered Dec 02 '12 at 08:53

user207421

305,947
44
307
483

complexity of quick sort algorithm

3 Answers3