k vs k-th in sort.texi

Martin Jansche jansche@ling.ohio-state.edu
Sun Mar 2 22:05:00 GMT 2003


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



More information about the Gsl-discuss mailing list