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: James Theiler <jt at lanl dot gov>
- To: Brian Gough <bjg at network-theory dot co dot uk>
- Cc: gsl-discuss <gsl-discuss at sources dot redhat dot com>
- Date: Sun, 2 Mar 2003 14:44:37 -0700 (MST)
- Subject: Re: k vs k-th in sort.texi
On Sun, 2 Mar 2003, Brian Gough wrote:
] Thanks for the doc patch, now applied.
Thanks Brian, for your untiring efforts.
] I think you are right about
] needing workspace (or destroying the input array) to get the k-th
] largest.
By an odd coincidence, 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 is a
kind of partial sort of the array. if A[] is the array,
and n=6, then after the partial sort, one has that
A[6] has the value that it would have with a full sort
A[0],...,A[5] are all <= A[6], but it is not necessarily
the case that A[0]...A[5] are sorted among themselves
and A[6] <= A[7],...A[N-1]
This is not quite the same as our gsl_sort_smallest, which would put
the six smallest elements into a separate sorted list. STL provides
another function, called partial_sort, which is a lot more like
what the GSL provides.
I am of the school that says you shouldn't implement something unless
you need it, but this does seem like a nifty function for the GSL to
provide. More details in Austern's book, Generic Programming and the
STL, Addison-Wesley, 1999, Section 13.1.5.
jt
---------------------------------------------
James Theiler jt at lanl dot gov
MS-D436, NIS-2, LANL tel: 505/665-5682
Los Alamos, NM 87545 fax: 505/665-4414
----- Space and Remote Sensing Sciences -----