Databases
StackOverflow2013
Postsdbo
POMedian select algorithm - does it find the absolute median, or a "median of medians" close to the absolute median?
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POMedian select algorithm - does it find the absolute median, or a "median of medians" close to the absolute median?
    text
    copied!<p>Section 9.3 in CLRS 3rd edition "Selection in worst-case linear time" talks about the "Select" algorithm (sometimes called the BFPRT algorithm due to Blum, Floyd, Pratt, Rivest, and Tarjan) for finding the median of a list in O(n) time at worst case. I got a little confused as I tried to run a sample on the whiteboard. I understand that a certain number of elements can be eliminated at each call to "Select" (I have read 30% are eliminated versus 70% that need to be checked again), what I was confused about was which part of the array can be eliminated, i.e. if the array is visualized as a matrix with height 5 and width n/5, then which quadrant(s) do the eliminated elements rest in? I originally thought it was two diagonally adjacent quadrants but now I am thinking it is only one quadrant depending on what the median of medians is (see steps 5, 6, and 7 <a href="http://www.cs.cmu.edu/afs/cs/academic/class/15499-s09/www/scribe/lec8/lec8.pdf" rel="nofollow">here</a>).</p> <p>So I went to wikipedia to see if there was a quick explanation with less analysis than CLRS (for the sake of understanding the algorithm before I jumped back to CLRS for the analysis). I came to <a href="http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm" rel="nofollow">this</a>, particularly 'Finally, the "median of medians' is chosen to be the pivot." from the sound of the description in wikipedia, "Select" does not find the true median rather a element that is median-enough for the purpose of choosing a pivot for quicksort.</p> <p>So what does "Select" do in terms of the true median, and how does it do it? The phrase that comes to mind through all of this is "partial hierarchy", which as I understand, is the reason "Select" works, but by what logic can you eliminate elements from the list from being the median based on this partial hierarchy? </p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload