Algorithms For Dummies

 Challenging Difficult Problems

Ordering faster with Quicksort

Chapter 7 explains ordering algorithms, the true foundations of all the modern 

computer-based algorithmic knowledge. The Quicksort algorithm, which can run 

in logarithmic time but sometimes fails and produces results in quadratic time 

under ill-conditioned inputs, will surely amaze you. This section explores the rea-

sons why this algorithm may fail and provides an effective solution by injecting 

randomness into it. You start by examining the following code:

def quicksort(series, get):

    try:

        global operations

        operations 

+= len(series)

    except:pass

    if len(series) <= 3:

        return sorted(series)

    pivot = get(series)

    duplicates = series.count(pivot)

    left, right = list(),list()

    for item in series:

        if item < pivot:

            left.append(item)

FIGURE 17-5: 

Displaying Monte 

Carlo simulations 

as input grows.

---

CHAPTER 17