Clifford Heath wrote:
> Marcin Raczkowski wrote:
>> There are reaserch papers that descripbe O(nlogn) instead of (nlog^2n) 
>> algorithms but They are usually full of complex math and 20-50 pages 
>> long. Also one that i could understand Is based n pointers and 
>> interlinked lists and it's kinda hard to implement in Ruby
> 
> The wikipedia page for kdtrees references an o(n) median-finding algorithm
> in a book compiled by Cormen and others. I have the book, and the algorithm
> doesn't look too scary. I might have a go at implementing it. But in any
> case, the exact median is only needed if you demand an exactly-balanced 
> tree.
> Subsequent insertions will unbalance the tree anyhow in most cases, so it's
> probably not necessary.
> 
> The algorithm for finding the i'th lowest entry given in the book is as 
> follows.
> (copyright, fair use provisions allow posting):
> 
> The SELECT algorithm determines the ith smallest of an input array of n 
>  > 1 elements by
> executing the following steps. (If n = 1, then SELECT merely returns its 
> only input value as
> the ith smallest.)
> 1. Divide the n elements of the input array into n/5 groups of 5 
> elements each and at
> most one group made up of the remaining n mod 5 elements.
> 2. Find the median of each of the n/5 groups by first insertion 
> sorting the elements of
> each group (of which there are at most 5) and then picking the median 
> from the sorted
> list of group elements.
> 3. Use SELECT recursively to find the median x of the n/5 medians 
> found in step 2.
> (If there are an even number of medians, then by our convention, x is 
> the lower
> median.)
> 4. Partition the input array around the median-of-medians x using the 
> modified version of
> PARTITION. Let k be one more than the number of elements on the low side 
> of the
> partition, so that x is the kth smallest element and there are n-k 
> elements on the high
> side of the partition.
> 5. If i = k, then return x. Otherwise, use SELECT recursively to find 
> the ith smallest
> element on the low side if i < k, or the (i - k)th smallest element on 
> the high side if i >
> k.
> 
> That's it, not too scary.
> 
> Clifford Heath.
> 
> 

I didn't say it was scary, I'm not scared of complex math but since 
finals are coming soon I don't have enought time.

I didn't have this book, and other sources were pretty confusing 
(Reserch papers tend to be this way) - after i understood the algorithm 
writing Ruby implementation was piece of cake

Anyway thanks for posting this piece of article, I'll try to implement 
it ASAP.

about finding median - my algorithm doesn't find it either, but problem 
is to find a fast way to select (with some degree of aproximation) 
elements that were assigned to current branch