quick sort and O(nlgn) worst case bound
in [General Programming]
|
From: Ben Bacarisse on 5 Jan 2010 12:56 Willem <willem(a)stack.nl> writes: > 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 ? 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. [1] The first restriction on the algorithms considered is: "Pick a data item as pivot. We assume that this phase uses O(1) comparisons" <snip> -- Ben.
From: Richard Harter on 5 Jan 2010 13:02 On Tue, 5 Jan 2010 17:40:15 +0000 (UTC), Willem <willem(a)stack.nl> wrote: >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 ? Correct, sort of. (There are O(N) median algorithms but they are impractical.) > >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. Not at all. The idea is very simple. All you really know is that the elements in the "small" segment are smaller than the pivot and the ones in the "large" segment are larger than the pivot. I am the oracle. You use an O(1) algorithm to pick the pivot. I produce one element that is "small". All of the rest are "large" but you don't get to see them. Pivot selection looks at k elements for some fixed k. At each step I only need to produce k+1 elements. When we are all done we have generated a data set that will be O(n^2). It's a standard oracle argument. 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.
From: Willem on 5 Jan 2010 13:24 Richard Harter wrote: ) On Tue, 5 Jan 2010 17:40:15 +0000 (UTC), Willem <willem(a)stack.nl> ) wrote: )>Median pivot selection is O(N), isn't it ? ) ) Correct, sort of. (There are O(N) median algorithms but they are ) impractical.) Practicality is not an issue. The question is if median pivot selection is in O(1), which it clearly isn't. )>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. ) ) Not at all. The idea is very simple. All you really know is ) that the elements in the "small" segment are smaller than the ) pivot and the ones in the "large" segment are larger than the ) pivot. I am the oracle. You use an O(1) algorithm to pick the ) pivot. I produce one element that is "small". All of the rest ) are "large" but you don't get to see them. Oh I see. You only get to know the result of the comparison, and not the actual element itself, which can then be changed later (as long as you don't change the results of any of the comparisons). 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: Daniel Pitts on 5 Jan 2010 15:38 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). -- Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>
From: Richard Harter on 5 Jan 2010 16:38
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. 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. |