Algorithms For Dummies

  Using Randomized Algorithms 

     337

        if item > pivot:

            right.append(item)

    return quicksort(left, get) 

+ [pivot

            ] * duplicates 

+ quicksort(right, get)

This is another implementation of the algorithm from Chapter 7. However, this 

time the code extracts the function that decides the pivot the algorithm uses to 

recursively split the initial list. The algorithm decides the split by taking the first 

list value. It also tracks how many operations it takes to complete the ordering 

using the 

operations

 global variable, which is defined, reset, and accessed as a 

counter  outside  the  function.  The  following  code  tests  the  algorithm,  under 

unusual conditions, requiring it to process an already ordered list. Note its 

performance:

series = list(range(25))

operations = 0

sorted_list = quicksort(series, choose_leftmost)

print ("Operations: %i" % operations)

Operations: 322

In this case, the algorithm takes 322 operations to order a list of 25 elements, 

which is horrid performance. Using an already ordered list causes the problem 

because the algorithm splits the list into two lists: an empty one and another one 

with the residual values. It has to repeat this unhelpful split for all the unique 

values present in the list. Usually the Quicksort algorithm works fine because it 

works with unordered lists, and picking the leftmost element is equivalent to 

randomly drawing a number as the pivot. To avoid this problem, you can use a 

variation of the algorithm that provides a true random draw of the pivot value.

def choose_random(l): return choice(l)

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

operations = 0

sorted_list = quicksort(series, choose_random)

print ("Operations: %i" % operations)

Operations: 81

Now the algorithm performs its task using a lower number of operations, which is 

exactly the running time 

n * log(n)

 that is 

25 * log(25) = 80.5

.

---

---

CHAPTER 18