This is the mail archive of the
gsl-discuss@sources.redhat.com
mailing list for the GSL project.
Re: k vs k-th in sort.texi
- From: Martin Jansche <jansche at ling dot ohio-state dot edu>
- To: James Theiler <jt at lanl dot gov>
- Cc: <gsl-discuss at sources dot redhat dot com>
- Date: Sun, 2 Mar 2003 17:04:57 -0500 (EST)
- Subject: Re: k vs k-th in sort.texi
On Sun, 2 Mar 2003, James Theiler wrote:
> I stumbled across a related function in the STL. It is called the
> nth_element, and it claims to be O(N) where N is the size of the
> full array.
It's most likely a variant of the linear-time selection algorithm
described in Knuth AoCP vol. 3, or in Cormen/Leiserson/Rivest ch. 10.
I think it would be useful to have in GSL. As a further example, in
addition to gsl_stats_median_from_sorted_data (which is O(1) after
O(n*log(n)) sorting) one could have a linear time function
gsl_stats_median.
- martin