Re: [Caml-list] kth smallest element

["Dário Abdulrehman" <drehman31@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 1363 bytes --]

This is not a trivial problem as can be seen here:

http://en.wikipedia.org/wiki/Selection_algorithm
http://www.derekroconnor.net/home/MMS406/Sorting.pdf

Bruno, I think the modified quicksort explained in the PDF is more efficient
than using a min-heap.



On 1/16/07, Bruno De Fraine <Bruno.De.Fraine@vub.ac.be> wrote:
>
> On 15 Jan 2007, at 20:56, Jon Harrop wrote:
> > Anyone got code for the kth smallest element in a list that I can
> > borrow?
>
> I have code for a set that can be limited to a certain size. While
> you add a potentially very large number of elements, the set will
> retain the 30 largest elements it has seen up to that point (given
> that the set was initialized with bound 30). You could modify the
> code to keep track of the smallest elements instead.
>
> Regards,
> Bruno
>
>
>
>
>
> --
> Bruno De Fraine
> Vrije Universiteit Brussel
> Faculty of Applied Sciences, INFO - SSEL
> Room 4K208, Pleinlaan 2, B-1050 Brussels
> tel: +32 (0)2 629 29 75
> fax: +32 (0)2 629 28 70
> e-mail: Bruno.De.Fraine@vub.ac.be
>
>
>
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>
>
>
>

[-- Attachment #2: Type: text/html, Size: 2127 bytes --]