#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
def recQuickSort(left, right):
if right-left <= 0: #if size is 1,
return #it's already sorted
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
def recQuickSort(left, right):
if right-left <= 0: #if size <= 1,
return # already sorted
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()
#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,
return # already sorted
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