How to find the median of a one-dimensional array?

Question

Programming

Greetings. How to find the median of an array without sorting first?

Answer 1

Once upon a time, I stole a quick search for the median from a book with a collection of snippets. Here is the code . It does not perform a complete sorting, but only looks for the median. If you work with pointers, then when calculating the moving median, the calculations are accelerated.

Answer 2

topic on habré
in your case k = [n / 2]

Answer 3

If the set of values ​​of the array elements (0..255) is known in advance, and the number of elements is much larger than the set of values ​​(several thousand), you can use the histogram - count the number of elements of each value (5 zeros, 340 ones, 210 twos ...) Find the middle in the histogram much simpler (the total number will be known, it is enough to sum the quantities in the cells until half of the total number is exceeded. The element on which the middle will be reached and will be the median)
This approach greatly speeds up the median filtering of images with a large radius only "edges" when moving to a neighboring pixel)