Hi Petr, Maybe this will give inspiration http://en.wikipedia.org/wiki/Selection_algorithm
It seems to me, that you just need a selection algorithm which works in O(n * k) time for k arbitrary elements. If you combine O(n*k) selection algorithm with any O(n * lg n) sort, you furfil your time constrain. Regards, Mads > Hi all, > > about a month ago, we were discussing sorting in Haskell with a friend. We > realized a nice property of lazy merge-sort (which is AFAIK the implementation > of Data.List.sort): Getting the first element of the sorted list actually > requires O(n) time, not O(n * log n) as in imperative languages. And > immediately we asked: Would it be possible to create a lazy selection/sorting > algorithm so that getting any element of the sorted list/array by its index > would require just O(n) time, and getting all the elements would still be in > O(n * log n)? > > More precisely: The result of sorting an n-element list or array should be a > structure that allows to ask i-th element of the result (for example, a lazy > array). Asking k arbitrary elements should take no more than > O(min(n * log n, k * n)) > > I believe that this could be done, but so far I wasn't able to implement and > show it myself. I think the solution would be somewhat modified lazy quicksort > (or "Median of Medians algorithm" if we want to be sure that we get good > pivots). > > Perhaps somebody else would also like to give it a try? Or perhaps explain me > why it's not possible? > > Best regards, > Petr > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe
signature.asc
Description: This is a digitally signed message part
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe