Quick Sort

In [25]:
%pprint
Pretty printing has been turned OFF
In [30]:
from rcviz import CallGraph, viz
In [29]:
from random import sample
nums = sample(range(1000), k=20)
nums
Out[29]:
[691, 878, 142, 952, 8, 419, 578, 991, 576, 709, 74, 655, 295, 647, 859, 403, 929, 268, 333, 396]
In [31]:
cg = CallGraph()
In [36]:
def quick_sort(alist):
    quick_sort_helper(alist, 0, len(alist)-1)
In [37]:
#@viz(cg)
def quick_sort_helper(alist, first, last):
    if first < last:
        splitpoint = partition(alist, first, last)
        
        quick_sort_helper(alist, first, splitpoint-1)
        quick_sort_helper(alist, splitpoint+1, last)
In [38]:
def partition(alist, first, last):
    pivotvalue = alist[first]
    
    leftmark = first+1
    rightmark = last
    
    done = False
    
    while not done:
        while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
            leftmark += 1
            
        while rightmark >= leftmark and alist[rightmark] >= pivotvalue:
            rightmark -= 1
            
        if rightmark < leftmark:
            done = True
        else:
            alist[leftmark], alist[rightmark] = alist[rightmark], alist[leftmark]
            
    alist[first], alist[rightmark] = alist[rightmark], alist[first]
    
    return rightmark
In [39]:
quick_sort(nums)
In [40]:
nums
Out[40]:
[8, 74, 142, 268, 295, 333, 396, 403, 419, 576, 578, 647, 655, 691, 709, 859, 878, 929, 952, 991]

CS Interlude: "short-circuiting"

In [16]:
l = [3,1,4,1,5,9]

if l[2] == 4:
    print("Found the number!")
Found the number!
In [17]:
l != [] and l[2] == 4
Out[17]:
True
In [18]:
l = []

if l[2] == 4:
    print("Found the number!")
---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
<ipython-input-18-74e95f0cebdb> in <module>
      1 l = []
      2 
----> 3 if l[2] == 4:
      4     print("Found the number!")

IndexError: list index out of range
In [19]:
l = []

if l and l[2] == 4:
    print("Found the number!")
In [22]:
l = []

# short circuiting the boolean AND if the first operand if F, 
# second operand isn't evaluated and the whole thing is false
if l != [] and l[2] == 4:
    print("Found the number!")
In [23]:
l != [] and l[2] == 4
Out[23]:
False
In [ ]:
l = []

# short circuiting the boolean AND if the first operand if F, 
# second operand isn't evaluated and the whole thing is false
if len(l) != 0 and l[2] == 4:
    print("Found the number!")