Median of Medians in Java?

I don't know if you still need this problem solved, but ics.uci.edu/~eppstein/161/960130.html has an algorithm: select(L,k) { if (L has 10 or fewer elements) { sort L return the element in the kth position } partition L into subsets Si of five elements each (there will be n/5 subsets total). For (i = 1 to n/5) do xi = select(Si,3) M = select({xi}, n/10) partition L into L1M if (k length(L1)+length(L2)) return select(L3,k-length(L1)-length(L2)) else return M } Good luck!

3 I know this is an old post, but the above implementation is not really the median of medians, since it contains a call to sort, it's worst case will be minimum O(nlgn). You need to find the median of each group of five using a constant number of comparisons (the problem I am looking to solve, I think I might have it, it uses 4 comparisons in every case. , I can't write it here, since it is on 44 lines!

If you et rid of the call to sort, this algorithm will be O(n) – Tom Jan 25 '10 at 15:33 1 @Tom: You are wrong, the above algorithm is guaranteed to have O(n) time complexity - see the link above or wikipedia for the proof. Besides, the sort is called (usually insertion sort) only when the range is less than 10, which just speeds up the algorithm, so for n > 10, the complexity is not O(n lg n). I also implemented this algorithm yesterday and it works great and in linear time (as expected).

– leden Feb 4 at 11:36.

I agree with the answer/solution from Chip Uni. I will just comment the sorting part and provide some further explanations: You do not need any sorting algorithm. The algorithm is similar to quicksort, with the difference that only one partition is solved (left or right).

We just need to find an optimal pivot so that left and right parts are as equal as possible, which would mean N/2 + N/4 + N/8 ... = 2N iterations, and thus the time complexity of O(N). The above algorithms, called median of medians, computes the median of medians of 5, which turns out to yield linear time complexity of the algorithm. However, sorting algorithm is used when the range being searched for nth smallest/greatest element (which I suppose you are implementing with this algorithm) in order to speed up the algorithm.

Insertion sort is particularly fast on small arrays up to 7 to 10 elements. Implementation note: M = select({xi}, n/10) actually means taking the median of all those medians of 5-element groups. You can accomplish that by creating another array of size (n - 1)/5 + 1 and call the same algorithm recursively to find the n/10-th element (which is median of the newly created array).

I know it's a very old post and you might not remember about it any more. But I wonder did you measure the running time of your implementation when you implemented it? I tried this algorithm and compare it with the simple approach using java sorting method (Arrays.sort() ), then pick the kth element from sorted array.

The result that I received is that this algorithm only out-beat java sorting algorithm when the size of the array is about hundred thousand elements or more. And it's only about 2 or 3 times faster, which is obviously not log(n) time faster. Do you have any comment on that?

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.