#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
#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