quick sort and O(nlgn) worst case bound
in [General Programming]
|
From: Daniel Pitts on 3 Jan 2010 15:01 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))" -- Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>
From: Jon Harrop on 5 Jan 2010 11:22 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? -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/?u
From: Ben Bacarisse on 5 Jan 2010 12:28 Jon Harrop <jon(a)ffconsultancy.com> writes: > 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? Yes, given a sound definition of all the terms, but the paper uses a non-standard view of the input (and, consequently, of the whole problem of comparison sorting). From the abstract: "Quicksort can be made to go quadratic by constructing input on the fly in response to the sequence of items compared." I.e. there is no know input until the end of the sort! You can't apply the O(1) median algorithm in such circumstances (actually I am guessing here -- I assume you can't but I have not checked). -- Ben.
From: Willem on 5 Jan 2010 12:40 Ben Bacarisse wrote: ) Yes, given a sound definition of all the terms, but the paper uses a ) non-standard view of the input (and, consequently, of the whole ) problem of comparison sorting). From the abstract: ) ) "Quicksort can be made to go quadratic by constructing input on the ) fly in response to the sequence of items compared." ) ) I.e. there is no know input until the end of the sort! You can't ) apply the O(1) median algorithm in such circumstances (actually I am ) guessing here -- I assume you can't but I have not checked). Median pivot selection is O(N), isn't it ? Constructing input in the fly seems nonsense anyway, the very first division will compare (and thus fix) all the elements, so you can't influence any of the following divisions. SaSW, Willem -- Disclaimer: I am in no way responsible for any of the statements made in the above text. For all I know I might be drugged or something.. No I'm not paranoid. You all think I'm paranoid, don't you ! #EOT
From: Richard Harter on 5 Jan 2010 12:39
On Tue, 05 Jan 2010 16:22:19 +0000, Jon Harrop <jon(a)ffconsultancy.com> 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? It is confusing. Briefly: (1) Pete said (paraphrased) that no quicksort (except introsort) was O(n log n) worst case - at least as far as he knew. (2) Stephen Howe misread what Pete wrote. He understood Pete to be asserting that quicksort was O(n log n) worst case. He pointed to a process for generating a counter example for pivot methods that are O(1). (3) Richard Harter (that's me) pointed out that Stephen had misread what Pete had written. (4) Stephen Howe agreed that he had misread Pete - quite understandably, I will add. Pete's wording was a trifle obscure. (5) Jon Harrop (that's you) pointed out that quicksort using a median pivot is O(n log n). ----- There is a nomenclature problem here. The term, quicksort, denotes a family of algorithms defined by a general pattern, to wit: (a) Use some method for selecting one element as a pivot. (b) Compare each element with the pivot. (c) Use the comparison result to divide the data into segments. There can be 2 or 3 segments, depending on variant. (d) Order the segments. (e) Apply the procedure recursively to each segment not equal to the pivot. It is well known that the worst case behaviour of quicksort algorithms depends upon the method used for pivot selection. Thus the worst case is O(n^2) if the pivot selection method is O(1). It is O(n log n) if (A) the method is O(n) at worst and (B) there is some constant theta such that the segment with the fewest elements has at least theta*n elements. (The wording gets more complicated for fat pivots). HTH. HAND. Richard Harter, cri(a)tiac.net http://home.tiac.net/~cri, http://www.varinoma.com Infinity is one of those things that keep philosophers busy when they could be more profitably spending their time weeding their garden. |