Selection Algorithm to Find Median

Question

Possible Duplicate:
How to calculate or approximate the median of a list without storing the list

I want to apply using C# an algorithm to find the median value using selection/quick sort. But I do not want to sort the whole array in order to get the median.

Can I do it?

Why would you NOT WANT to sort the whole array? I think it is mandatory to sort the whole array as it is the keypoint for finding the exact median (not guess the probable median).. — Abbas, Nov 24 '11 at 16:30
The posted link isn't [tag:C#] specifically, however the algorithm could easily be applied. — George Duckett, Nov 24 '11 at 16:31
@George the link does not seem to be working it link to the whole C# tag!! — Mohamad Ibrahim, Nov 24 '11 at 16:39
You do not have to sort the whole array. Each time you have to sort only half of the array. — vharavy, Nov 24 '11 at 18:47
The supposed duplicate question link is for approximate, not exact median. Not sure how that blunder slipped in here. — Frank Hileman, May 17 '16 at 16:57

score 1 · Accepted Answer · answered Nov 24 '11 at 19:41

1

Wikipedia's entry on Selection Algorithm gives various alternatives, including the Median of Medians approach, which would seem to fit your requirements. In particular, it has a worst-case performance of O(n).

answered Nov 24 '11 at 19:41

Matthew Strawbridge

19,940
10
72
93

Selection Algorithm to Find Median

1 Answers1