Example 7.1 Page no : 321¶

In [1]:


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

A= 35 47 88 24 10 98 14 75 97 38
A= 10 14 24 35 38 47 75 88 97 98


Example 7.2 Page No 327¶

In [2]:

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

A= 114 43 4 72 43 6 41 78 25 107 19 18 191 116 108 10
Pivot is  99 , Partition is at index  9
A= 114 108 4 116 43 191 41 107 25 78 19 18 6 72 43 10


Example 7.3 Page no : 337¶

In [3]:

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,
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.

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

A= 63 42 31 37 74 79 6 76 0 5 7 6 82 48 26 70
A= 0 5 6 6 7 26 31 37 42 48 63 70 74 76 79 82


Example 7.4 Page No : 347¶

In [4]:

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.

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

A= 93 28 45 24 83 16 56 62 26 13 62 49 29 89 63 18
A= 13 16 18 18 24 26 28 28 29 45 45 62 62 63 83 83


Example 7.5 Page No : 351¶

In [5]:

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.

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

A= 32 49 43 84 84 76 63 70 37 50 13 46 46 19 60 72
A= 13 19 32 32 37 43 46 49 50 60 63 70 70 76 84 84

In [ ]: