Algorithms For Dummies

  Using Randomized Algorithms 

     333

    return quickselect(right, k)

quickselect(series, 250)

14.0

The algorithm works well because it keeps reducing the problem size. It works 

best when the random pivot number is drawn nearer to the kth position (the stop-

ping rule is that the pivot number is the value in the kth position). Unfortunately, 

because you can’t know the kth position in the unordered list, drawing randomly 

by using a uniform distribution (each element in the list has the same chance of 

being chosen) is the best solution because the algorithm eventually finds the right 

solution. Even when random chance doesn’t work in the algorithm’s favor, the 

algorithm keeps on reducing the problem, thus getting more chances to find the 

solution, as demonstrated earlier in the chapter when guessing the cards ran-

domly  picked  from  a  deck.  As  the  deck  gets  smaller,  guessing  the  answer  gets 

easier. The following code shows how to use Quickselect to determine the median 

of a list of numbers:

def median(series):

    if len(series) % 2 != 0:

        return quickselect(series, len(series)//2)

    else:

        left  = quickselect(series, (len(series)-1) // 2)

        right = quickselect(series, (len(series)

+1) // 2)

        return (left 

+ right) / 2

median(series)

14.0