Version française
Home     About     Download     Resources     Contact us    
Browse thread
kth smallest element
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Dário_Abdulrehman <drehman31@g...>
Subject: Re: [Caml-list] kth smallest element
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
>
>
>
>