The median-of-medians algorithm is a deterministic, worst-case O(n)-time algorithm for the selection problem (given a list of values, find the kth largest value). The constant factor in the O(n) is large, and the algorithm is not commonly used in practice.
Questions tagged [median-of-medians]
70 questions
65
votes
2 answers
Understanding "median of medians" algorithm
I want to understand "median of medians" algorithm on the following example:
We have 45 distinct numbers divided into 9 group with 5 elements each.
48 43 38 33 28 23 18 13 8
49 44 39 34 29 24 19 14 9
50 45 40 35 30 25 20 15 10
51 46 41 36 31 26…
simon
- 1,405
- 1
- 15
- 24
19
votes
2 answers
Why is the median-of-medians algorithm described as using O(1) auxiliary space?
Wikipedia lists the median-of-medians algorithm as requiring O(1) auxiliary space.
However, in the middle of the algorithm, we make a recursive call on a subarray of size n/5 to find the median of medians. When this recursive call returns, we use…
John Kurlak
- 6,594
- 7
- 43
- 59
15
votes
1 answer
Explanation of the Median of Medians algorithm
The Median of medians approach is very popular in quicksort type partitioning algorithms to yield a fairly good pivot, such that it partitions the array uniformly. Its logic is given in Wikipedia as:
The chosen pivot is both less than and greater…
SexyBeast
- 7,913
- 28
- 108
- 196
10
votes
3 answers
Find a median of N^2 numbers having memory for N of them
I was trying to learn about distributed computing and came across a problem of finding median of a large set of numbers:
Assume that we have a large set of numbers (lets say number of elements is N*K) that cannot fit into memory (size N). How do we…
Akshya11235
- 959
- 4
- 11
- 25
7
votes
2 answers
Not understanding median of medians algorithm to find k-th element
Below is my code for trying to understand the median of medians algorithm (using blocks of size 5). I understand how to get medians of the input, but I'm not sure how to code the block to keep recursing the input until I just have the median. Then…
Emmanuel Mudiay
- 123
- 6
5
votes
4 answers
Worst-case O(n) algorithm for doing k-selection
Apart from the median-of-medians algorithm, is there any other way to do k-selection in worst-case O(n) time? Does implementing median-of-medians make sense; I mean, is the performance advantage good enough for practical purposes ?
Harman
- 1,571
- 1
- 19
- 31
5
votes
3 answers
Dividing the elements of an array in 3 groups
I have to divide the elements of an array into 3 groups. This needs to be done without sorting the array. Consider the example
we have 120 unsorted values thus the smallest 40 values need to be in the first group and next 40 in the second and the…
nishant mehta
- 109
- 1
- 10
4
votes
2 answers
Median of median algorithms understanding
I've searched around the web and visited the wiki page for the Median of median algorithm. But can't seem to find an explicit statement to my question:
If one has a very very large list of integers (TBs in size) and wants to find the median of this…
Jared Krumsie
- 397
- 1
- 8
- 17
4
votes
2 answers
Median of Medians algorithm misunderstanding?
What I understand already
I understand that median of medians algorithm(I will denote as MoM) is a high constant factor O(N) algorithm. It finds the medians of k-groups(usually 5) and uses them as the next iteration's sets to find medians of. The…
OneRaynyDay
- 3,658
- 2
- 23
- 56
4
votes
1 answer
Where does the constant 5 come from in the median-of-medians algorithm?
I've been trying to understand where the "5" comes from in the Median of Medians algorithm, but can't seem to find a simple description of how it is derived and why it is optimal.
For example, why isn't say 7 a viable option?
The only advantage I…
Rikardo Koder
- 672
- 9
- 16
3
votes
2 answers
Something I dont understand about median of medians algorithm
There is something I don't understand about the algorithm of median of medians.
One key step about this algorithm is to find an approximate median, and according to Wikipedia, we have the guarantee that this approximate median is greater than 30%…
Truc Truca
- 79
- 6
3
votes
2 answers
Stack overflow error with Quicksort and median implementation
First of all I'm just going to state that this is a homework question which I have made an extensive amount of attempts on.
I've been asked to modify quicksort in Java to set the pivot as the psuedo median of 9 values in the array using the formula…
Habitat
- 709
- 11
- 23
3
votes
1 answer
Median of Medians space complexity
I implemented an nth_number selection algorithm using Medians of Medians.
On wikipedia, it states that it's space complexity is O(1)
I had to store the medians in a temporary array in order to find the median amongst those medians. How would you be…
Kamran224
- 1,584
- 7
- 20
- 33
2
votes
1 answer
Generalizing the median of medians algorithm
I am asked to find the run time of the general form of the median of medians algorithm for groups of size g. It seems from common examples g=3,5,7 with T(n)=T(n/5)+T(2n/3)+cn, T(n)=T(n/5)+T(7n/10)+cn, and T(n)=T(n/7)+T(5n/7)+cn, respectively, that…
Robin McManus
- 23
- 3
2
votes
1 answer
Multiple Count and Median Values from a Dataframe
I am trying to perform several operations in one program at same time.
I have a data-frame that has Dates of which I have no clue of start and end and I want to find:
Total number of days the data-set has
Total number of hours
Median of the…
Sitz Blogz
- 1,061
- 6
- 30
- 54