Algorithms For Dummies

Doing simulations using Monte Carlo

As part of understanding the Quickselect algorithm, it pays to know how it works 

internally. By setting a counter inside the 

quickselect

 function, you can check 

performance under different conditions using a Monte Carlo simulation:

def quickselect(series, k, counter=0):

    pivot = choice(series)

    left, right = list(),list()

    for item in series:

        if item < pivot:

---

334

 

   

  PART 5 

 Challenging Difficult Problems

            left.append(item)

        if item > pivot:

            right.append(item)

    counter 

+= len(series)

    length_left = len(left)

    if length_left > k:

        return quickselect(left, k, counter)

    k -= length_left

    duplicates = series.count(pivot)

    if duplicates > k:

        return float(pivot), counter

    k -= duplicates

    return quickselect(right, k, counter)

The first experiment tries to determine how many operations the algorithm needs, 

on average, to find the median of an input list of 1001 numbers:

results = list()

for run in range(1000):

    n = 1001

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

    median,count = quickselect(series, n//2)

    assert(median==np.median(series))

    results.append(count)

print ("Mean operations: %i" % np.mean(results))

Mean operations: 2764

Displaying the results on a histogram (see Figure 17-4) reveals that the algorithm 

computes from two to four times the size of the input, with three times being the 

most likely number of processed computations.

import matplotlib.pyplot as plt

%matplotlib inline

plt.hist(results, bins='auto')

plt.xlabel("Computations")

plt.ylabel("Frequency")

plt.show()

---

CHAPTER 17