Win a copy of Escape Velocity: Better Metrics for Agile Teams this week in the Agile and Other Processes forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Tim Cooke
  • Paul Clapham
  • Jeanne Boyarsky
Sheriffs:
  • Ron McLeod
  • Frank Carver
  • Junilu Lacar
Saloon Keepers:
  • Stephan van Hulst
  • Tim Moores
  • Tim Holloway
  • Al Hobbs
  • Carey Brown
Bartenders:
  • Piet Souris
  • Frits Walraven
  • fred rosenberger

Quick sort's worst case

 
Ranch Hand
Posts: 63
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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?
 
Sheriff
Posts: 7113
184
Eclipse IDE Postgres Database VI Editor Chrome Java Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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?
 
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
 
Montana has cold dark nights. Perfect for the heat from incandescent light. Tiny ad:
Garden Master Course kickstarter
https://coderanch.com/t/754577/Garden-Master-kickstarter
reply
    Bookmark Topic Watch Topic
  • New Topic