tag:blogger.com,1999:blog-8082954141980125536.post3244727978510394054..comments2008-01-02T22:29:29.238-05:00rschttp://www.blogger.com/profile/06357099531993534337noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-8082954141980125536.post-62071041398294265152008-01-02T22:29:00.000-05:002008-01-02T22:29:00.000-05:002008-01-02T22:29:00.000-05:00I'm shocked, really ... selecting the median is a well-studied problem. Here are bounds for common/textbook algorithms and "state of the art".<BR/><BR/>Determinisitic:<BR/>Median of medians: 10n<BR/>Schonhage et al.: 3n<BR/>-Lower bound: 2n<BR/><BR/>Randomized:<BR/>Hoare's: 4n<BR/>LazySelect: 1.5nnikolascohttp://nikolasco.livejournal.com/noreply@blogger.comtag:blogger.com,1999:blog-8082954141980125536.post-38696871670667252212008-01-02T21:25:00.000-05:002008-01-02T21:25:00.000-05:002008-01-02T21:25:00.000-05:00I see, from the source...<BR/><BR/> <I> 2. The pivot-choosing phase uses O(1) comparisons.<BR/><BR/> 3. Partitioning is a contiguous phase of n-O(1) comparisons, all<BR/> against the same pivot value. </I>Adam Fokkenhttp://www.blogger.com/profile/17269061341779276519noreply@blogger.comtag:blogger.com,1999:blog-8082954141980125536.post-32291021854192327082008-01-02T21:20:00.000-05:002008-01-02T21:20:00.000-05:002008-01-02T21:20:00.000-05:00Does it matter how the quicksort algorithm picks its "pivot"?Adam Fokkenhttp://www.blogger.com/profile/17269061341779276519noreply@blogger.com