• Post Reply Bookmark Topic Watch Topic
  • New Topic

Quick sort's worst case  RSS feed

 
Aron Silvester
Ranch Hand
Posts: 63
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Quick sort in its worst case is O(n^2). I read on another forum that one of the example for a worst case for a quick sort is "Array is already sorted in same order".

Does this mean that if you implement a quick sort on an array that is already sorted will result in a worst case?
 
Knute Snortum
Sheriff
Posts: 4270
127
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I believe that's correct if you're using the first element as your pivot.
 
Aron Silvester
Ranch Hand
Posts: 63
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Knute Snortum wrote:I believe that's correct if you're using the first element as your pivot.


Alright, this is the first time I'm learning this sorting algorithm so It's kind of confusing. I thought of another case, where the pivot always chosen were always the highest or lowest value in the array. This will result in a worst case for a quick sort, which would be 0(n^2). One such case would be the array {8,7,6,5,4,3,2}. 8 is the pivot and we put it in its right place in the array, with elements smaller than the pivot before it, and larger elements after it. The next iteration will look like {7,6,4,4,3,2,8}. The next pivot will be 7 and the next iteration will be {6,5,4,3,2,7,8}. This goes on until they are sorted from least to greatest, which results in n^2 comparison, the worst case for a quick sort.

Agree or disagree?
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Conrado Sanchez wrote:Agree or disagree?

It looks right; but of course you can short-circuit that by selecting the your pivots at random. I believe there are also versions that try to ensure that you select a "good-quality" pivot, but I've forgotten exactly how they go about it.

Winston
 
Don't get me started about those stupid light bulbs.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!