quick sort and O(nlgn) worst case bound
in [General Programming]
|
From: Daniel Pitts on 5 Jan 2010 19:04 Richard Harter wrote: > On Tue, 05 Jan 2010 12:38:12 -0800, Daniel Pitts > <newsgroup.spamfilter(a)virtualinfinity.net> wrote: > >> Jon Harrop wrote: >>> Daniel Pitts wrote: >>>> Richard Harter wrote: >>>>> On Sun, 03 Jan 2010 18:55:14 +0000, Stephen Howe >>>>> <sjhoweATdialDOTpipexDOTcom> wrote: >>>>>> On Mon, 21 Dec 2009 07:55:22 -0500, pete <pfiland(a)mindspring.com> wrote: >>>>>>>> But this is academic. If you use Musser's hybrid Introsort, it wil lbe >>>>>>>> Quicksort with O(1) pivots and Heapsort where it blows >>>>>>>> up. That guarantees O(N * lg N) performance in worst case and close to >>>>>>>> Quicksort in the average case. >>>>>>> Outside of introsort, I'm unfamiliar with any quicksort >>>>>>> which is truly O(N * log(N)) for worst case. >>>>>> Then feed your sort functions the adversary from >>>>>> http://www.cs.dartmouth.edu/~doug/mdmspe.pdf >>>>>> >>>>>> I think you will find they blow up (anything that is using a O(1) method >>>>>> to get a pivot). >>>>> I hope that if you reread the material you commented on you will >>>>> see the true value of your comment. >>>> I misread the context myself. I'm not sure if it was because it was a >>>> hidden double negative ("Outside of" + "unfamiliar"), or just the way >>>> the line wraps, but the message was easily misinterpreted as "quicksort >>>> have worst case (N*log(N))" >>> I'm confused by this discussion. Quicksort with median pivot is O(n log n), >>> right? >> Did you read the document linked above? >> >> If the pivot is chosen in O(1) time, then a data-set could cause a >> pathological condition and quicksort's performance would degrade to near >> n^2 time complexity, instead of n log n. >> >> If you make pivot selection an O(N) operation, then quicksort >> automatically becomes O(N^2) (actually becomes worse than selection sort). > > This is incorrect. A moment's reflection should show you why. > Hint: What is the cost of partitioning. Ah, I see. I was forgetting the order of operations. Partitioning is O(N). So, if picking the "best" pivot is O(N), you end up with the loop being N+N, which is still O(N). Then you still have divide and conquer, so O(N log N). You end up with about the same constant multiplier as heapsort, which is approximately 2 * N log N. I wonder what the time overhead for building a balanced tree would be. Would that be about the same as 2 * N log N? I know the space required would increase. -- Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>
From: Pascal J. Bourguignon on 5 Jan 2010 18:22 Daniel Pitts <newsgroup.spamfilter(a)virtualinfinity.net> writes: > If the pivot is chosen in O(1) time, then a data-set could cause a > pathological condition and quicksort's performance would degrade to > near n^2 time complexity, instead of n log n. The pivot could be choose randomly (in O(1)). However, the input set could still be (2 2 2 2 2 2 ... 2), so that a blind quick sort could still be O(n�). > If you make pivot selection an O(N) operation, then quicksort > automatically becomes O(N^2) (actually becomes worse than selection > sort). -- __Pascal Bourguignon__ http://www.informatimago.com/
From: Jon Harrop on 6 Jan 2010 20:16 Ben Bacarisse wrote: > Yes. I was thinking about the bounds quoted in the paper[1] and wrote > that instead! So, quite apart from what I wrote, any algorithm for > picking the median that is not O(1) is excluded so the paper does > apply to all quicksorts. The paper does not apply to all quicksorts. -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/?u
From: Alf P. Steinbach on 6 Jan 2010 19:17 * Jon Harrop: > Ben Bacarisse wrote: >> Yes. I was thinking about the bounds quoted in the paper[1] and wrote >> that instead! So, quite apart from what I wrote, any algorithm for >> picking the median that is not O(1) is excluded so the paper does >> apply to all quicksorts. > > The paper does not apply to all quicksorts. > There was a paper once by I think it was Doug McIlroy, showing how to dynamically foil any quicksort, forcing it to qudratic time. :-) Cheers, - Alf
From: Moi on 6 Jan 2010 19:28
On Thu, 07 Jan 2010 01:17:38 +0100, Alf P. Steinbach wrote: > * Jon Harrop: >> Ben Bacarisse wrote: >> >> The paper does not apply to all quicksorts. >> >> > There was a paper once by I think it was Doug McIlroy, showing how to > dynamically foil any quicksort, forcing it to qudratic time. :-) > Yes. A link was posted in this thread a few days ago. (Steven Howe, Sunday 18:55 UTC) HTH, AvK |