[Haskell-cafe] excercise - a completely lazy sorting algorithm

[Mads Lindstrøm]

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 at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 197 bytes
Desc: This is a digitally signed message part
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20090706/ef7756ef/attachment.bin