# 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!")