Algorithms For Dummies

Calculating a median using Quickselect

Calculating a statistical measure, the median, can prove challenging when you 

work on unsorted input lists. In fact, a median relies on the position of your data 

when it is ordered:

FIGURE 17-3: 

Displaying the 

results of a 

Monte Carlo 

simulation.

---

CHAPTER 17

  Using Randomized Algorithms 

     331

 

»

If the data inputs have an odd number of elements, the median is exactly the 

middle value.

 

»

If the data inputs have an even number of elements, the median is the 

average of the pair of middle numbers in the ordered input list.

A median is like a mean, a single value that can represent a distribution of values. 

The median, based on the input vector element order, isn’t influenced much by 

the values present in your list. It’s simply the middle value. Instead, the values 

present  at  the  head  and  tail  of  the  input  can  influence  the  mean  when  they’re 

extremely small or large. This robustness makes the median very helpful in many 

situations when using statistics. A simple example of a median calculation using 

Python functions helps you understand this measure. (You can find this code in 

the 

A4D; 17; Quickselect.ipynb

 file on the Dummies site as part of the down-

loadable code; see the Introduction for details.)

from random import randint, random, choice

import numpy as np

import sys

sys.setrecursionlimit(1500)

n = 501

series = [randint(1,25) for i in range(n)]

print ('Median is %0.1f' % np.median(series))

Median is 14.0

The code creates a list of 501 elements and obtains the list median using the 

median

 

function  from  the  NumPy  package.  The  reported  median  is  actually  the  middle 

point of the ordered list, which is the 251st element:

print ('251st element of the ordered series is %0.1f' %

       sorted(series)[250])

251st element of the ordered series is 14.0

Ordering the list and extracting the necessary element demonstrates how 

median

 

works. Because ordering is involved in calculating a median, you can expect a best 

running time of 

O(n*log(n))

. By using randomization provided by the Quickse-

lect algorithm, you can get an even better result, a running time of 

O(n)

. Quick-

select works recursively, which is why you must set a higher recursion limit in 

Python, given a list and the position of the value needed from an ordered list. 

---

332

 

   

  PART 5