Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!samsung!noose.ecn.purdue.edu!iuvax!purdue!haven!mimsy!brillig.cs.umd.edu!gasarch
From: gasarch@brillig.cs.umd.edu (William Ian Gasarch)
Newsgroups: comp.theory
Subject: Finding Median of $n$, $n$ SMALL.
Message-ID: <26930@mimsy.umd.edu>
Date: 11 Oct 90 02:12:49 GMT
Sender: news@mimsy.umd.edu
Reply-To: gasarch@brillig.cs.umd.edu (William Ian Gasarch)
Organization: U of Maryland, Dept. of Computer Science, Coll. Pk., MD 20742
Lines: 14

In KNUTH Vol. 3 (Page 215) he has a table for the BEST (in terms
or worse case) number of comparisons to find the $k$th largest
of $n$ numbers, where $1\le k \le n \le 10$.

Does anyone out there know if the table has been improved
or extended?  Or if anyone has worked out the best algorithm
for average case performance.

I am talking about VERY SMALL $n$, so the usual algorithms
may not suffice.

Please email responses to gasarch@cs.umd.edu

					bill