k vs k-th in sort.texi
James Theiler
jt@lanl.gov
Sun Mar 2 21:44:00 GMT 2003
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@lanl.gov
MS-D436, NIS-2, LANL tel: 505/665-5682
Los Alamos, NM 87545 fax: 505/665-4414
----- Space and Remote Sensing Sciences -----
More information about the Gsl-discuss
mailing list