On 4/13/07, Ian Lynagh
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)
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..]