# Quick Sort¶

In :
%pprint

Pretty printing has been turned OFF

In :
from rcviz import CallGraph, viz

In :
from random import sample
nums = sample(range(1000), k=20)
nums

Out:
[691, 878, 142, 952, 8, 419, 578, 991, 576, 709, 74, 655, 295, 647, 859, 403, 929, 268, 333, 396]
In :
cg = CallGraph()

In :
def quick_sort(alist):
quick_sort_helper(alist, 0, len(alist)-1)

In :
#@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 :
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 :
quick_sort(nums)

In :
nums

Out:
[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 :
l = [3,1,4,1,5,9]

if l == 4:
print("Found the number!")

Found the number!

In :
l != [] and l == 4

Out:
True
In :
l = []

if l == 4:
print("Found the number!")

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

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

if l and l == 4:
print("Found the number!")

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 l != [] and l == 4:
print("Found the number!")

In :
l != [] and l == 4

Out:
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 == 4:
print("Found the number!")