# 14: Improving Quicksort¶

## Example 1: Page 283¶

In [1]:
#demonstrates quick sort with median-of-three partitioning
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
size = right-left+1
if size <= 3:	#manual sort if small
self.manualSort(left, right)
else:	#quicksort if large
median = self.medianOf3(left, right)
partition = self.partitionIt(left, right, median)
self.recQuickSort(left, partition-1)	#sort left side
self.recQuickSort(partition+1, right)	#sort right side
#end recQuickSort()

def medianOf3(self, left, right):
center = (left + right)/2
#order left & center
if self._theVect[left] > self._theVect[center]:
self.swap(left, center)
#order left & right
if self._theVect[left] > self._theVect[right]:
self.swap(left, right)
#order center & right
if self._theVect[center] > self._theVect[right]:
self.swap(center, right)

self.swap(center, right - 1)	#put pivot on right
return self._theVect[right - 1]	#return median value
#end medianOf3()

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

def partitionIt(self, left, right, pivot):
leftMark = left	#left (after+=)
rightMark = right - 1#right-1 (after -=)
while True:
leftMark += 1
while self._theVect[leftMark] < pivot:	#find bigger
leftMark += 1
rightMark -= 1
while self._theVect[rightMark] > pivot:	#find smaller
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 - 1)	#restore pivot
return leftMark	#return pivot location
#end paritionIt()

def manualSort(self, left, right):
size = right-left+1
if size <= 1:
return	#no sort necessary
if size == 2:
if self._theVect[left] > self._theVect[right]:
self.swap(left, right)
return
else:	#size==3, so 3-sort left, center (right-1) & right
if self._theVect[left] > self._theVect[right-1]:
self.swap(left, right-1)	#left, center

if self._theVect[left] > self._theVect[right]:
self.swap(left, right)	#left, right

if self._theVect[right-1] > self._theVect[right]:
self.swap(right-1, right) 	#center, right
#end manualSort()
#end class ArrayIns

arr = ArrayIns()	#create the 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= [10, 6, 99, 26, 87, 43, 41, 48, 70, 21, 89, 65, 42, 48, 14, 7]
A= [6, 7, 10, 14, 21, 26, 41, 42, 43, 48, 48, 65, 70, 87, 89, 99]


## Example 2: Page 287¶

In [2]:
#demonstrates quick sort; uses insertion sort for cleanup
from random import randrange	#for randrange()

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._theArray = []	#array theArray

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

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

def quickSort(self):	#sort the array
self.recQuickSort(0, len(self._theArray) - 1)
#self.insertionSort(0, len(self._theVect) - 1)	#(another option)

def recQuickSort(self, left, right):	#recursive sort
size = right-left+1
if size < 10:	#manual sort if small
self.insertionSort(left, right)
else:	#quicksort if large
median = self.medianOf3(left, right)
partition = self.partitionIt(left, right, median)
self.recQuickSort(left, partition-1)
self.recQuickSort(partition+1, right)
#end recQuickSort()

def medianOf3(self, left, right):
center = (left + right)/2
#order left & center
if self._theArray[left] > self._theArray[center]:
self.swap(left, center)
#order left & right
if self._theArray[left] > self._theArray[right]:
self.swap(left, right)
#order center & right
if self._theArray[center] > self._theArray[right]:
self.swap(center, right)

self.swap(center, right - 1)	#put pivot on right
return self._theArray[right - 1]	#return median value
#end medianOf3()

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

def partitionIt(self, left, right, pivot):
leftMark = left	#right of first element
rightMark = right - 1#left of pivot
while True:
leftMark += 1
while self._theArray[leftMark] < pivot:	#find bigger
leftMark += 1
rightMark -= 1
while self._theArray[rightMark] > pivot:	#find smaller
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 - 1)	#restore pivot
return leftMark	#return pivot location
#end paritionIt()

def insertionSort(self, left, right):	#insertion sort
#sorted on left of out
for out in range(left+1, right+1):
temp = self._theArray[out]	#remove marked item
#using In as in is reserved in Python
In = out	#start shifts at out
#until one is smaller,
while In > left and self._theArray[In-1] > temp:
self._theArray[In] = self._theArray[In -1]	#shift item to right
In -= 1#go left one position
self._theArray[In] = temp	#insert marked item
#end for
#end insertionSort()
#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= [29, 13, 61, 25, 80, 64, 70, 72, 40, 53, 78, 32, 73, 36, 72, 88]
A= [13, 25, 29, 32, 36, 40, 53, 61, 64, 70, 72, 72, 73, 78, 80, 88]