quick sort and O(nlgn) worst case bound
in [General Programming]
|
From: Willem on 28 Nov 2009 13:53 mohangupta13 wrote: ) On Nov 28, 9:12�pm, Willem <wil...(a)stack.nl> wrote: )> Yes, but practically speaking that well defined algorithm is quite slow. ) ) But here I was referring theoretical consideration All practical implementations of quicksort don't use the median, so that is the version of quicksort that people will be talking about, in theoretical considerations also. 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: James Dow Allen on 29 Nov 2009 03:06 On Nov 28, mohangupta13 <mohangupt...(a)gmail.com> wrote: > Using median of median or just median to choose the pivot in quick > sort it can be deterministically proved that the worst case running > time of quicksort is O(nlgn) and not O(n^2) . There's an algorithm to find medians with *average* O(n) cost, and that leads directly to ordinary quicksort. You're speaking of the *guaranteed* O(n) median finder, which is, I think, significantly slower *on average* than the simple median finder. > So why is that quick sort is still blamed to be having a worst case of > O(n^2).?? I believe Willem's responses were correct, but response from a different perspective might have been less confusing. The sort you imply -- call it mohansort -- would indeed be a O(n log n) sort based on quick-sort. But there are other sorts that are O(n log n) that would be faster on average, because you've sacrificed the big advantages of quicksort: coding simplicity and fast *average* speed. (Perhaps a sorting algorithm should detect that it's encountered pathological input (e.g. size after 4 divisions > 1/2 original size when expected size is 1/16) and switch to a guaranteed O(n log n) method....) A few days ago, Ben gave a link to a very interesting paper by Bentley which discussed the tuning of quicksort, and fixes for various worst-case inputs. (I suppose Bentley-sort itself still has some worst-case, O(n^2)-yielding input; perhaps the black hats have engineered such data to use in a denial-of-service attack!) James
From: robertwessel2 on 30 Nov 2009 17:33 On Nov 29, 2:06 am, James Dow Allen <jdallen2...(a)yahoo.com> wrote: > (Perhaps a sorting algorithm should detect that it's encountered > pathological input (e.g. size after 4 divisions > 1/2 original > size when expected size is 1/16) and switch to a guaranteed > O(n log n) method....) That would be Introsort. Basically uses Quicksort until a run of bad (as in not very productive) partitioning operations is detected (using a fairly straight-forward method of comparing the partition size and the depth of the partition tree - basically what you suggested), then switches to heap sort for that partition. David Musser's original Introsort paper is worth reading just for the analysis of just how easy it is to actually generate datasets with pathological partitioning characteristics.
From: Stephen Howe on 2 Dec 2009 15:11 On Sat, 28 Nov 2009 07:23:35 -0800 (PST), mohangupta13 <mohangupta13(a)gmail.com> wrote: >hello all , >Using median of median or just median to choose the pivot in quick >sort it can be deterministically proved that the worst case running >time of quicksort is O(nlgn) and not O(n^2) . > >So why is that quick sort is still blamed to be having a worst case of >O(n^2).?? >Is there some problem with the above mentioned methods of choosing the >pivot ? Yes, they are O(N). All those O(N) calls add up. Most pivots for Quicksort are chosen in O(1) 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. Stephen Howe
From: Stephen Howe on 2 Dec 2009 15:19
On Sun, 29 Nov 2009 00:06:11 -0800 (PST), James Dow Allen <jdallen2000(a)yahoo.com> wrote: >A few days ago, Ben gave a link to a very interesting paper >by Bentley which discussed the tuning of quicksort, and fixes >for various worst-case inputs. (I suppose Bentley-sort itself >still has some worst-case, O(n^2)-yielding input; perhaps >the black hats have engineered such data to use in a >denial-of-service attack!) > >James Yes. See http://www.cs.dartmouth.edu/~doug/mdmspe.pdf which is an engineered comparison function for feeding into C's qsort() If the C's qsort() is based on quicksort, even well-engineered quicksort (like Bentley's), it guarantees quadratic behaviour. I think it is proven that all quicksorts that choose a pivot in O(1) will have a worst-case. Stephen Howe |