class ArraySh:
def __init__(self,m): # constructor
self.theArray = [] # create the array
self.nElems = 0 # no items yet
def insert(self,value): # put element into array
self.theArray.append(value) # insert it
self.nElems+=1 # increment size
def display(self): # displays array contents
print 'A=' ,
for j in range(self.nElems): # for each element,
print self.theArray[j] , # display it
print ''
def shellSort(self):
inner = 0
outer = 0
temp = 0
h = 1
while(h <= self.nElems/3):
h = h*3 + 1
while(h>0):
# find initial value of h
# (1, 4, 13, 40, 121, ...)
# decreasing h, until h=1
# h-sort the file
for outer in range(h,self.nElems):
temp = self.theArray[outer]
inner = outer
# one subpass (eg 0, 4, 8)
while(inner > h-1 and self.theArray[inner-h] >= temp):
self.theArray[inner] = self.theArray[inner-h]
inner -= h
self.theArray[inner] = temp
h = (h-1) / 3
maxSize = 10 # array size
arr = ArraySh(maxSize) # create the array
import random
for j in range(maxSize): # fill array with
# random numbers
n = int(random.random()*99)
arr.insert(n)
arr.display() # display unsorted array
arr.shellSort() # shell sort the array
arr.display() # display sorted array
class ArrayPar:
def __init__(self,m): # constructor
self.theArray = [] # create the array
self.nElems = 0 # no items yet
def insert(self,value): # put element into array
self.theArray.append(value) # insert it
self.nElems += 1 # increment size
def size(self): # return number of items
return self.nElems
def display(self): # displays array contents
print 'A=' ,
for j in range(self.nElems): # for each element,
print self.theArray[j] , # display it
print ''
def partitionIt(self,left,right,pivot):
leftPtr = left - 1 # right of first elem
rightPtr = right + 1 # left of pivot
while(True):
leftPtr += 1
while(leftPtr < right ):
leftPtr += 1
if self.theArray[leftPtr] < pivot:
break
while(rightPtr > left ):# find smaller item
rightPtr -= 1
if self.theArray[rightPtr] > pivot:
break;
if(leftPtr >= rightPtr): # if pointers cross,
break
else: # not crossed, so
self.swap(leftPtr, rightPtr)
return leftPtr
def swap(self,dex1,dex2): # swap two elements
temp = self.theArray[dex1] # A into temp
self.theArray[dex1] = self.theArray[dex2] # B into A
self.theArray[dex2] = temp # temp into BPartitioning
maxSize = 16 # array size
arr = ArrayPar(maxSize) # create the array
import random
for j in range(maxSize): # fill array with
# random numbers
n = int(random.random()*199)
arr.insert(n)
arr.display() # display unsorted array
pivot = 99 # pivot value
print "Pivot is ", pivot ,
size = arr.size() # partition array
partDex = arr.partitionIt(0, size-1, pivot)
print ", Partition is at index " , partDex
arr.display() # display partitioned array
class ArrayIns:
def __init__(self,m):
self.theArray = [] # create the array
self.nElems = 0 # no items yet
def insert(self,value): # put element into array
self.theArray.append( value) # insert it
self.nElems += 1 # increment size
def display(self): # displays array contents
print 'A=' ,
for j in range(self.nElems): # for each element,
print self.theArray[j] , # display it
print ''
def quickSort(self):
self.recQuickSort(0, self.nElems-1)
def recQuickSort(self,left,right):
if(right-left <= 0): # if size <= 1,
return # already sorted
else: # size is 2 or larger
pivot = self.theArray[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
def partitionIt(self,start, end,pivot):
bottom = start-1 # Start outside the area to be partitioned
top = end # Ditto
done = 0
while not done: # Until all elements are partitioned...
while not done: # Until we find an out of place element...
bottom = bottom+1 # ... move the bottom up.
if bottom == top: # If we hit the top...
done = 1 # ... we are done.
break
if self.theArray[bottom] > pivot: # Is the bottom out of place?
self.theArray[top] = self.theArray[bottom] # Then put it at the top...
break # ... and start searching from the top.
while not done: # Until we find an out of place element...
top = top-1 # ... move the top down.
if top == bottom: # If we hit the bottom...
done = 1 # ... we are done.
break
if self.theArray[top] < pivot: # Is the top out of place?
self.theArray[bottom] = self.theArray[top] # Then put it at the bottom...
break # ...and start searching from the bottom.
self.theArray[top] = pivot # Put the pivot in its place.
return top # Return the split point
maxSize = 16 # array size
arr = ArrayIns(maxSize) # create array
import random
for j in range(maxSize): # fill array with
# random numbers
n = int(random.random()*99)
arr.insert(n)
arr.display() # display items
arr.quickSort() # quicksort them
arr.display() # display them again
class ArrayIns:
def __init__(self,m):
self.theArray = [] # create the array
self.nElems = 0 # no items yet
def insert(self,value): # put element into array
self.theArray.append(value) # insert it
self.nElems+=1 # increment size
def display(self): # displays array contents
print 'A=' ,
for j in self.theArray:
print j ,
print ''
def quickSort(self):
self.recQuickSort(0, self.nElems-1)
def recQuickSort(self,left,right):
size = right-left+1
if(size <= 3): # manual sort if small
self.manualSort(left, right)
else:
median = self.medianOf3(left, right)
partition = self.partitionIt(left, right, median)
self.recQuickSort(left, partition-1)
self.recQuickSort(partition+1, right)
def partitionIt(self,start, end,pivot):
bottom = start-1 # Start outside the area to be partitioned
top = end # Ditto
done = 0
while not done: # Until all elements are partitioned...
while not done: # Until we find an out of place element...
bottom = bottom+1 # ... move the bottom up.
if bottom == top: # If we hit the top...
done = 1 # ... we are done.
break
if self.theArray[bottom] > pivot: # Is the bottom out of place?
self.theArray[top] = self.theArray[bottom] # Then put it at the top...
break # ... and start searching from the top.
while not done: # Until we find an out of place element...
top = top-1 # ... move the top down.
if top == bottom: # If we hit the bottom...
done = 1 # ... we are done.
break
if self.theArray[top] < pivot: # Is the top out of place?
self.theArray[bottom] = self.theArray[top] # Then put it at the bottom...
break # ...and start searching from the bottom.
self.theArray[top] = pivot # Put the pivot in its place.
return top # Return the split point
def medianOf3(self,left, right):
center = (left+right)/2 # order left & center
if( self.theArray[left] > self.theArray[center] ):
self.theArray[left],self.theArray[center] = self.theArray[center],self.theArray[left]
if( self.theArray[left] > self.theArray[right] ):
self.theArray[left],self.theArray[right] = self.theArray[right],self.theArray[left]
if( self.theArray[center] > self.theArray[right] ):
self.theArray[right],self.theArray[center] = self.theArray[center],self.theArray[right]
self.theArray[right-1],self.theArray[center] = self.theArray[center],self.theArray[right-1] # put pivot on right
return self.theArray[right-1] # return median value
def manualSort(self,left,right):
size = right-left+1
if(size <= 1):
return # no sort necessary
if(size == 2): # 2-sort left and right
if( self.theArray[left] > self.theArray[right] ):
self.theArray[right],self.theArray[left] = self.theArray[left],self.theArray[right]
return
else: # size is 3
# 3-sort left, center, & right
if( self.theArray[left] > self.theArray[right-1] ):
self.theArray[right-1],self.theArray[left] = self.theArray[left],self.theArray[right-1] # left, center
if( self.theArray[left] > self.theArray[right] ):
self.theArray[right],self.theArray[left] = self.theArray[left],self.theArray[right] # left, right
if( self.theArray[right-1] > self.theArray[right] ):
self.theArray[right-1],self.theArray[right] = self.theArray[right],self.theArray[right-1] # center, right
maxSize = 16 # array size
arr = ArrayIns(maxSize) # create array
import random
for j in range(maxSize): # fill array with
# random numbers
n = int(random.random()*99)
arr.insert(n)
arr.display() # display items
arr.quickSort() # quicksort them
arr.display() # display them again
class ArrayIns:
def __init__(self,m):
self.theArray = [] # create the array
self.nElems = 0 # no items yet
def insert(self,value): # put element into array
self.theArray.append(value) # insert it
self.nElems+=1 # increment size
def display(self): # displays array contents
print 'A=' ,
for j in self.theArray:
print j ,
print ''
def quickSort(self):
self.recQuickSort(0, self.nElems-1)
def recQuickSort(self,left,right):
size = right-left+1
if(size <= 10):
self.insertionSort(left, right)
else:
median = self.medianOf3(left, right)
partition = self.partitionIt(left, right, median)
self.recQuickSort(left, partition-1)
self.recQuickSort(partition+1, right)
def partitionIt(self,start, end,pivot):
bottom = start-1 # Start outside the area to be partitioned
top = end # Ditto
done = 0
while not done: # Until all elements are partitioned...
while not done: # Until we find an out of place element...
bottom = bottom+1 # ... move the bottom up.
if bottom == top: # If we hit the top...
done = 1 # ... we are done.
break
if self.theArray[bottom] > pivot: # Is the bottom out of place?
self.theArray[top] = self.theArray[bottom] # Then put it at the top...
break # ... and start searching from the top.
while not done: # Until we find an out of place element...
top = top-1 # ... move the top down.
if top == bottom: # If we hit the bottom...
done = 1 # ... we are done.
break
if self.theArray[top] < pivot: # Is the top out of place?
self.theArray[bottom] = self.theArray[top] # Then put it at the bottom...
break # ...and start searching from the bottom.
self.theArray[top] = pivot # Put the pivot in its place.
return top # Return the split point
def medianOf3(self,left, right):
center = (left+right)/2 # order left & center
if( self.theArray[left] > self.theArray[center] ):
self.theArray[left],self.theArray[center] = self.theArray[center],self.theArray[left]
if( self.theArray[left] > self.theArray[right] ):
self.theArray[left],self.theArray[right] = self.theArray[right],self.theArray[left]
if( self.theArray[center] > self.theArray[right] ):
self.theArray[right],self.theArray[center] = self.theArray[center],self.theArray[right]
self.theArray[right-1],self.theArray[center] = self.theArray[center],self.theArray[right-1] # put pivot on right
return self.theArray[right-1] # return median value
def insertionSort(self,left,right):
i = 0
out = 0 # sorted on left of out
for out in range(left+1,right+1):
temp = self.theArray[out] # remove marked item
i = out # start shifts at out
# until one is smaller,
while(i >left and self.theArray[i-1] >= temp):
self.theArray[i] = self.theArray[i-1] # shift item to right
i -= 1 # go left one position
self.theArray[i] = temp # insert marked item
maxSize = 16 # array size
arr = ArrayIns(maxSize) # create array
import random
for j in range(maxSize): # fill array with
# random numbers
n = int(random.random()*99)
arr.insert(n)
arr.display() # display items
arr.quickSort() # quicksort them
arr.display() # display them again