# 13: Quicksort¶

## Example 1: Page 260¶

In [1]:
#demonstrates partitioning an array
from random import randrange	#for random numbers

class ArrayPar:
def __init__(self):	#special method to create objects
#with instances customized to a specific initial state

#as private instance variables don't exist in Python,
#hence using a convention: name prefixed with an underscore, to treat them as non-public part
self._theVect = []	#list

def insert(self, value):	#put element into array
self._theVect.append(value)	#insert it

def getSize(self):	#return number of items
return len(self._theVect)

def display(self):	#display array contents
print 'A=', self._theVect	#display it

#partition a range
def partitionIt(self, left, right, pivot):
leftMark = left - 1#right of first elem
rightMark = right + 1#left of pivot
while True:
leftMark += 1
while leftMark < right and self._theVect[leftMark] < pivot:	#find bigger item
leftMark += 1

rightMark -= 1
while rightMark > left and self._theVect[rightMark] > pivot:	#find smaller item
rightMark -= 1
if leftMark >= rightMark:	#if markers cross,
break	#partition done
else:	#not crossed, so
self.swap(leftMark, rightMark)	#swap elements
#end while(True)
return leftMark	#return partition
#end paritionIt()

def swap(self, dex1, dex2):	#swap two elements
self._theVect[dex1], self._theVect[dex2] = self._theVect[dex2], self._theVect[dex1]
#end swap()
#end class ArrayPar

arr = ArrayPar()	#create the array

for j in xrange(16):	#fill array with
n = randrange(0, 200)	#random numbers
arr.insert(n)
arr.display()	#display unsorted array

pivot = 99	#pivot value
print 'Pivot is', pivot,
size = arr.getSize()
#partition array
partDex = arr.partitionIt(0, size - 1, pivot)

print 'Partition is at index', partDex
arr.display()	#display partitioned array
#end

A= [196, 174, 16, 52, 180, 12, 73, 116, 188, 4, 95, 132, 107, 165, 137, 59]
Pivot is 99 Partition is at index 7
A= [59, 95, 16, 52, 4, 12, 73, 116, 188, 180, 174, 132, 107, 165, 137, 196]


## Example 2: Page 265¶

In [2]:
def recQuickSort(left, right):
if right-left <= 0:	#if size is 1,
else:	#size is 2 or larger
#partition range
partition = partitionIt(left, right)
recQuickSort(left, partition-1)	#sort left side
recQuickSort(partition+1, right)	#sort right side


## Example 3: Page 269¶

In [3]:
def recQuickSort(left, right):
if right-left <= 0:	#if size <= 1,
else:	#size is 2 or larger
pivot = theArray[right]	#rightmost item
#partition range
partition = partitionIt(left, right, pivot)
recQuickSort(left, partition-1)	#sort left side
recQuickSort(partition+1, right)	#sort right side
#	end recQuickSort()


## Example 4: Page 270¶

In [4]:
#demonstrates simple version of quick sort
from random import randrange	#for random numbers

class ArrayIns:
def __init__(self):	#special method to create objects
#with instances customized to a specific initial state

#as private instance variables don't exist in Python,
#hence using a convention: name prefixed with an underscore, to treat them as non-public part
self._theVect = []	#list

def insert(self, value):	#put element into array
self._theVect.append(value)	#insert it

def display(self):	#displays array contents
print 'A=', self._theVect	#display it

def quickSort(self):	#sort array
self.recQuickSort(0, len(self._theVect) - 1)	#call recursive sort

def recQuickSort(self, left, right):	#recursive sort
if right-left <= 0:	#if size <= 1,
else:	#size is 2 or larger
pivot = self._theVect[right]	#rightmost item
#partition range
partition = self.partitionIt(left, right, pivot)
self.recQuickSort(left, partition-1)	#sort left side
self.recQuickSort(partition+1, right)	#sort right side
#	end recQuickSort()

def partitionIt(self, left, right, pivot):
leftMark = left-1	#left (after+=)
rightMark = right#right-1 (after -=)
while True:
#find bigger item
leftMark += 1
while self._theVect[leftMark] < pivot:
leftMark += 1
#find smaller item
rightMark -= 1
while rightMark > 0 and self._theVect[rightMark] > pivot:
rightMark -= 1

if leftMark >= rightMark:	#if pointers cross,
break	#partition done
else:	#not crossed, so
self.swap(leftMark, rightMark)	#swap elements
#end while(True)
self.swap(leftMark, right)	#restore pivot
return leftMark	#return pivot location
#end paritionIt()

def swap(self, dex1, dex2):	#swap two elements
self._theVect[dex1], self._theVect[dex2] = self._theVect[dex2], self._theVect[dex1]
#end swap()
#end class ArrayIns

arr = ArrayIns()	#create array

for j in xrange(16):	#fill array with
n = randrange(0, 100)	#random numbers
arr.insert(n)
arr.display()	#display items
arr.quickSort()	#quicksort them
arr.display()	#display them again
#end

A= [6, 11, 6, 20, 39, 51, 70, 24, 13, 31, 55, 74, 96, 18, 70, 68]
A= [6, 6, 11, 13, 18, 20, 24, 31, 39, 51, 55, 68, 70, 70, 74, 96]