Selection 

The median of an array of N values is the middle value in order of magnitude, for example, the median of 4, 2, 5, 3, 1 is 3. The median is a special case of the more general selection problem which is to return the value having a given rank in order of magnitude. (The smallest value has rank 1, the largest has rank N, and the median has rank ceiling(N / 2).) One way to solve the selection problem is to sort the given values (in O(N log(N))time) and return the rank^{th} member of the sorted array. However this method does more work then is necessary and there are faster algorithms. A method that usually runs in O(N)time makes use of the partition algorithm from quicksort: Partition the array into "smaller" and "larger" values. If the desired rank is somewhere within the larger values repeat the process on that section only, otherwise repeat it on the smaller values only. The problem is solved when we arrive at a sub...subsection containing a single value. Note that in general the array has been changed but is not necessarily sorted. Recall that when working on a section of an array, partition first makes a guess at the median of that section. If the guess is good the section is divided into two roughly equal parts. If most guesses are good this version of select runs in O(N)time: N + f.N + f^{2}.N + ..., where 0 ≤ f < 1, equals N / (1  f). However if most guesses are bad it runs in O(N^{2})time. Blum et al [2] produced a selection algorithm that is guaranteed to run in lineartime. It divides the numbers into small "columns" (blocks) of size 'c' and finds the median of each column. It then finds the median of these medians, recursively. This yields a guaranteed good guess at the actual median which enables at least one quarter of the values to be eliminated from consideration (f ≤ 0.75). Their final algorithm makes at most 5.4305 N comparisons of elements. The javascript form runs three selection algorithms, (i) a (very) dumb algorithm as a check, (ii) the partitionbased quickselect [1], and (iii) a simple version of the first lineartime algorithm of Blum et al[2]. — Lloyd Allison 29/7/2018References
And also search for 'median selection problem' in the [bibliography]. 

↑ © L. Allison, www.allisons.org/ll/ (or as otherwise indicated). Created with "vi (Linux)", charset=iso88591, fetched Monday, 22Jul2024 23:25:25 UTC. Free: Linux, Ubuntu operatingsys, OpenOffice officesuite, The GIMP ~photoshop, Firefox webbrowser, FlashBlock flash on/off. 