Colin DeVilbiss cdevilbiss at gmail.com
Fri Apr 13 14:44:29 EDT 2007

On 4/13/07, Ian Lynagh <igloo at earth.li> wrote:

> Tuple each element with its position:                 O(n)
> Find kth smallest element in linear time, as per [1]: O(n)
> Filter list for elements <= kth smallest:             O(n)
> Sort filtered list by position:                       O(k log k)
> map snd to get the positions:                         O(k)
>
> Total: O(n + k log k)
>
> [1] http://en.wikipedia.org/wiki/Selection_algorithm

Inspired by the above, I thought I'd see about writing it.

Note that attaching the indices prevents equal items from
comparing equal.  I didn't feel like writing the code for a
special data type that ignored a second element for the
purposes of comparisons; that just means replacing
"zip" and "map send".

The user can add stability by selective use of reverse
within the continuation functions.

There should probably be strictness annotations somewhere,
and calls to "length" should probably be accumulated in
partition instead, but the idea should be sound (except for
the likelihood of a bad pivot).

partition cont _ [] lt eq gt = cont lt eq gt
partition cont p (x:xs) lt eq gt = case x `compare` p of
LT -> partition cont p xs (x:lt) eq gt
EQ -> partition cont p xs lt (x:eq) gt
GT -> partition cont p xs lt eq (x:gt)

qsort [] = []
qsort (x:xs) = partition qs' x xs [] [x] []
where qs' lt eq gt = qsort lt ++ (eq ++ qsort gt)

findfirst _ [] = []
findfirst k (x:xs) = partition ff' x xs [] [x] []
where
ff' lt eq gt = let { ll = length lt; lle = ll + length eq }
in  if k < ll       then findfirst k lt
else if k > lle then lt ++ eq ++ findfirst (k - lle) gt
else            lt ++ take (k - ll) eq

getSmallest k = qsort . findfirst k
getSmallestIndices k = map snd . getSmallest k . flip zip [0..]