{
"metadata": {
"name": "",
"signature": "sha256:a1b30e83d81b2cbf128e785184057c842d4480c1f2796f1d1e7e78372f935c78"
},
"nbformat": 3,
"nbformat_minor": 0,
"worksheets": [
{
"cells": [
{
"cell_type": "heading",
"level": 1,
"metadata": {},
"source": [
"Chapter 7 : Advanced Sorting "
]
},
{
"cell_type": "heading",
"level": 3,
"metadata": {},
"source": [
"Example 7.1 Page no : 321"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
" \n",
"\n",
"class ArraySh:\n",
" def __init__(self,m): # constructor\n",
" self.theArray = [] # create the array\n",
" self.nElems = 0 # no items yet\n",
"\n",
" def insert(self,value): # put element into array\n",
" self.theArray.append(value) # insert it\n",
" self.nElems+=1 # increment size\n",
"\n",
" def display(self): # displays array contents\n",
" print 'A=' , \n",
" for j in range(self.nElems): # for each element,\n",
" print self.theArray[j] , # display it\n",
" print ''\n",
"\n",
" def shellSort(self):\n",
" inner = 0\n",
" outer = 0\n",
" temp = 0\n",
" h = 1\n",
" while(h <= self.nElems/3):\n",
" h = h*3 + 1\n",
" while(h>0):\n",
" # find initial value of h\n",
" # (1, 4, 13, 40, 121, ...)\n",
" # decreasing h, until h=1\n",
" # h-sort the file\n",
" for outer in range(h,self.nElems):\n",
" temp = self.theArray[outer]\n",
" inner = outer\n",
" # one subpass (eg 0, 4, 8)\n",
" while(inner > h-1 and self.theArray[inner-h] >= temp):\n",
" self.theArray[inner] = self.theArray[inner-h]\n",
" inner -= h\n",
" self.theArray[inner] = temp\n",
" h = (h-1) / 3\n",
"\n",
"maxSize = 10 # array size\n",
"arr = ArraySh(maxSize) # create the array\n",
"import random\n",
"for j in range(maxSize): # fill array with\n",
" # random numbers\n",
" n = int(random.random()*99)\n",
" arr.insert(n)\n",
"\n",
"arr.display() # display unsorted array\n",
"arr.shellSort() # shell sort the array\n",
"arr.display() # display sorted array"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"A= 35 47 88 24 10 98 14 75 97 38 \n",
"A= 10 14 24 35 38 47 75 88 97 98 \n"
]
}
],
"prompt_number": 1
},
{
"cell_type": "heading",
"level": 3,
"metadata": {},
"source": [
"Example 7.2 Page No 327"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
" \n",
"class ArrayPar:\n",
" def __init__(self,m): # constructor\n",
" self.theArray = [] # create the array\n",
" self.nElems = 0 # no items yet\n",
"\n",
" def insert(self,value): # put element into array\n",
" self.theArray.append(value) # insert it\n",
" self.nElems += 1 # increment size\n",
"\n",
" def size(self): # return number of items\n",
" return self.nElems \n",
"\n",
" def display(self): # displays array contents\n",
" print 'A=' ,\n",
" for j in range(self.nElems): # for each element,\n",
" print self.theArray[j] , # display it\n",
" print ''\n",
"\n",
" def partitionIt(self,left,right,pivot):\n",
" leftPtr = left - 1 # right of first elem\n",
" rightPtr = right + 1 # left of pivot\n",
" while(True):\n",
" leftPtr += 1\n",
" while(leftPtr < right ):\n",
" leftPtr += 1\n",
" if self.theArray[leftPtr] < pivot:\n",
" break\n",
" while(rightPtr > left ):# find smaller item\n",
" rightPtr -= 1\n",
" if self.theArray[rightPtr] > pivot:\n",
" break;\n",
" if(leftPtr >= rightPtr): # if pointers cross,\n",
" break\n",
" else: # not crossed, so\n",
" self.swap(leftPtr, rightPtr)\n",
" return leftPtr\n",
"\n",
" def swap(self,dex1,dex2): # swap two elements\n",
" temp = self.theArray[dex1] # A into temp\n",
" self.theArray[dex1] = self.theArray[dex2] # B into A\n",
" self.theArray[dex2] = temp # temp into BPartitioning\n",
"\n",
"maxSize = 16 # array size\n",
"arr = ArrayPar(maxSize) # create the array\n",
"import random\n",
"for j in range(maxSize): # fill array with\n",
" # random numbers\n",
" n = int(random.random()*199)\n",
" arr.insert(n)\n",
"arr.display() # display unsorted array\n",
"pivot = 99 # pivot value\n",
"print \"Pivot is \", pivot ,\n",
"size = arr.size() # partition array\n",
"partDex = arr.partitionIt(0, size-1, pivot)\n",
"print \", Partition is at index \" , partDex \n",
"arr.display() # display partitioned array"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"A= 114 43 4 72 43 6 41 78 25 107 19 18 191 116 108 10 \n",
"Pivot is 99 , Partition is at index 9\n",
"A= 114 108 4 116 43 191 41 107 25 78 19 18 6 72 43 10 \n"
]
}
],
"prompt_number": 2
},
{
"cell_type": "heading",
"level": 3,
"metadata": {},
"source": [
"Example 7.3 Page no : 337"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
" \n",
"class ArrayIns:\n",
" def __init__(self,m):\n",
" self.theArray = [] # create the array\n",
" self.nElems = 0 # no items yet\n",
"\n",
" def insert(self,value): # put element into array\n",
" self.theArray.append( value) # insert it\n",
" self.nElems += 1 # increment size\n",
"\n",
" def display(self): # displays array contents\n",
" print 'A=' ,\n",
" for j in range(self.nElems): # for each element,\n",
" print self.theArray[j] , # display it\n",
" print ''\n",
" def quickSort(self):\n",
" self.recQuickSort(0, self.nElems-1)\n",
"\n",
" def recQuickSort(self,left,right):\n",
" if(right-left <= 0): # if size <= 1,\n",
" return # already sorted\n",
" else: # size is 2 or larger\n",
" pivot = self.theArray[right] # rightmost item\n",
" # partition range\n",
" partition = self.partitionIt(left, right, pivot)\n",
" self.recQuickSort(left, partition-1) # sort left side\n",
" self.recQuickSort(partition+1, right) # sort right side\n",
"\n",
" def partitionIt(self,start, end,pivot):\n",
" bottom = start-1 # Start outside the area to be partitioned\n",
" top = end # Ditto\n",
" done = 0\n",
" while not done: # Until all elements are partitioned...\n",
" while not done: # Until we find an out of place element...\n",
" bottom = bottom+1 # ... move the bottom up.\n",
" if bottom == top: # If we hit the top...\n",
" done = 1 # ... we are done.\n",
" break\n",
" if self.theArray[bottom] > pivot: # Is the bottom out of place?\n",
" self.theArray[top] = self.theArray[bottom] # Then put it at the top...\n",
" break # ... and start searching from the top.\n",
" while not done: # Until we find an out of place element...\n",
" top = top-1 # ... move the top down.\n",
" \n",
" if top == bottom: # If we hit the bottom...\n",
" done = 1 # ... we are done.\n",
" break\n",
" \n",
" if self.theArray[top] < pivot: # Is the top out of place?\n",
" self.theArray[bottom] = self.theArray[top] # Then put it at the bottom...\n",
" break # ...and start searching from the bottom.\n",
"\n",
" self.theArray[top] = pivot # Put the pivot in its place.\n",
" return top # Return the split point\n",
"\n",
"maxSize = 16 # array size\n",
"arr = ArrayIns(maxSize) # create array\n",
"import random\n",
"for j in range(maxSize): # fill array with\n",
" # random numbers\n",
" n = int(random.random()*99)\n",
" arr.insert(n)\n",
"arr.display() # display items\n",
"arr.quickSort() # quicksort them\n",
"arr.display() # display them again"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"A= 63 42 31 37 74 79 6 76 0 5 7 6 82 48 26 70 \n",
"A= 0 5 6 6 7 26 31 37 42 48 63 70 74 76 79 82 \n"
]
}
],
"prompt_number": 3
},
{
"cell_type": "heading",
"level": 3,
"metadata": {},
"source": [
"Example 7.4 Page No : 347"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
" \n",
"class ArrayIns:\n",
" def __init__(self,m):\n",
" self.theArray = [] # create the array\n",
" self.nElems = 0 # no items yet\n",
"\n",
" def insert(self,value): # put element into array\n",
" self.theArray.append(value) # insert it\n",
" self.nElems+=1 # increment size\n",
"\n",
" def display(self): # displays array contents\n",
" print 'A=' ,\n",
" for j in self.theArray:\n",
" print j , \n",
" print ''\n",
" \n",
" def quickSort(self):\n",
" self.recQuickSort(0, self.nElems-1)\n",
"\n",
" def recQuickSort(self,left,right):\n",
" size = right-left+1\n",
" if(size <= 3): # manual sort if small\n",
" self.manualSort(left, right)\n",
" else:\n",
" median = self.medianOf3(left, right)\n",
" partition = self.partitionIt(left, right, median)\n",
" self.recQuickSort(left, partition-1)\n",
" self.recQuickSort(partition+1, right)\n",
"\n",
" def partitionIt(self,start, end,pivot):\n",
" bottom = start-1 # Start outside the area to be partitioned\n",
" top = end # Ditto\n",
" done = 0\n",
" while not done: # Until all elements are partitioned...\n",
" while not done: # Until we find an out of place element...\n",
" bottom = bottom+1 # ... move the bottom up.\n",
" if bottom == top: # If we hit the top...\n",
" done = 1 # ... we are done.\n",
" break\n",
" if self.theArray[bottom] > pivot: # Is the bottom out of place?\n",
" self.theArray[top] = self.theArray[bottom] # Then put it at the top...\n",
" break # ... and start searching from the top.\n",
" while not done: # Until we find an out of place element...\n",
" top = top-1 # ... move the top down.\n",
" \n",
" if top == bottom: # If we hit the bottom...\n",
" done = 1 # ... we are done.\n",
" break\n",
" \n",
" if self.theArray[top] < pivot: # Is the top out of place?\n",
" self.theArray[bottom] = self.theArray[top] # Then put it at the bottom...\n",
" break # ...and start searching from the bottom.\n",
"\n",
" self.theArray[top] = pivot # Put the pivot in its place.\n",
" return top # Return the split point \n",
" \n",
" \n",
" \n",
" def medianOf3(self,left, right):\n",
" center = (left+right)/2 # order left & center\n",
" if( self.theArray[left] > self.theArray[center] ):\n",
" self.theArray[left],self.theArray[center] = self.theArray[center],self.theArray[left]\n",
" if( self.theArray[left] > self.theArray[right] ):\n",
" self.theArray[left],self.theArray[right] = self.theArray[right],self.theArray[left]\n",
" if( self.theArray[center] > self.theArray[right] ):\n",
" self.theArray[right],self.theArray[center] = self.theArray[center],self.theArray[right]\n",
" self.theArray[right-1],self.theArray[center] = self.theArray[center],self.theArray[right-1] # put pivot on right\n",
" return self.theArray[right-1] # return median value\n",
"\n",
" def manualSort(self,left,right):\n",
" size = right-left+1\n",
" if(size <= 1):\n",
" return # no sort necessary\n",
" if(size == 2): # 2-sort left and right\n",
" if( self.theArray[left] > self.theArray[right] ):\n",
" self.theArray[right],self.theArray[left] = self.theArray[left],self.theArray[right]\n",
" return\n",
" else: # size is 3\n",
" # 3-sort left, center, & right\n",
" if( self.theArray[left] > self.theArray[right-1] ):\n",
" self.theArray[right-1],self.theArray[left] = self.theArray[left],self.theArray[right-1] # left, center\n",
" if( self.theArray[left] > self.theArray[right] ):\n",
" self.theArray[right],self.theArray[left] = self.theArray[left],self.theArray[right] # left, right\n",
" if( self.theArray[right-1] > self.theArray[right] ):\n",
" self.theArray[right-1],self.theArray[right] = self.theArray[right],self.theArray[right-1] # center, right\n",
"\n",
"\n",
"maxSize = 16 # array size\n",
"arr = ArrayIns(maxSize) # create array\n",
"import random\n",
"for j in range(maxSize): # fill array with\n",
" # random numbers\n",
" n = int(random.random()*99)\n",
" arr.insert(n)\n",
"arr.display() # display items\n",
"arr.quickSort() # quicksort them\n",
"arr.display() # display them again"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"A= 93 28 45 24 83 16 56 62 26 13 62 49 29 89 63 18 \n",
"A= 13 16 18 18 24 26 28 28 29 45 45 62 62 63 83 83 \n"
]
}
],
"prompt_number": 4
},
{
"cell_type": "heading",
"level": 3,
"metadata": {},
"source": [
"Example 7.5 Page No : 351"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
" \n",
"class ArrayIns:\n",
" def __init__(self,m):\n",
" self.theArray = [] # create the array\n",
" self.nElems = 0 # no items yet\n",
"\n",
" def insert(self,value): # put element into array\n",
" self.theArray.append(value) # insert it\n",
" self.nElems+=1 # increment size\n",
"\n",
" def display(self): # displays array contents\n",
" print 'A=' ,\n",
" for j in self.theArray:\n",
" print j , \n",
" print ''\n",
" \n",
" def quickSort(self):\n",
" self.recQuickSort(0, self.nElems-1)\n",
"\n",
" def recQuickSort(self,left,right):\n",
" size = right-left+1\n",
" if(size <= 10): \n",
" self.insertionSort(left, right)\n",
" else:\n",
" median = self.medianOf3(left, right)\n",
" partition = self.partitionIt(left, right, median)\n",
" self.recQuickSort(left, partition-1)\n",
" self.recQuickSort(partition+1, right)\n",
"\n",
" def partitionIt(self,start, end,pivot):\n",
" bottom = start-1 # Start outside the area to be partitioned\n",
" top = end # Ditto\n",
" done = 0\n",
" while not done: # Until all elements are partitioned...\n",
" while not done: # Until we find an out of place element...\n",
" bottom = bottom+1 # ... move the bottom up.\n",
" if bottom == top: # If we hit the top...\n",
" done = 1 # ... we are done.\n",
" break\n",
" if self.theArray[bottom] > pivot: # Is the bottom out of place?\n",
" self.theArray[top] = self.theArray[bottom] # Then put it at the top...\n",
" break # ... and start searching from the top.\n",
" while not done: # Until we find an out of place element...\n",
" top = top-1 # ... move the top down.\n",
" \n",
" if top == bottom: # If we hit the bottom...\n",
" done = 1 # ... we are done.\n",
" break\n",
" \n",
" if self.theArray[top] < pivot: # Is the top out of place?\n",
" self.theArray[bottom] = self.theArray[top] # Then put it at the bottom...\n",
" break # ...and start searching from the bottom.\n",
"\n",
" self.theArray[top] = pivot # Put the pivot in its place.\n",
" return top # Return the split point \n",
" \n",
" \n",
" \n",
" def medianOf3(self,left, right):\n",
" center = (left+right)/2 # order left & center\n",
" if( self.theArray[left] > self.theArray[center] ):\n",
" self.theArray[left],self.theArray[center] = self.theArray[center],self.theArray[left]\n",
" if( self.theArray[left] > self.theArray[right] ):\n",
" self.theArray[left],self.theArray[right] = self.theArray[right],self.theArray[left]\n",
" if( self.theArray[center] > self.theArray[right] ):\n",
" self.theArray[right],self.theArray[center] = self.theArray[center],self.theArray[right]\n",
" self.theArray[right-1],self.theArray[center] = self.theArray[center],self.theArray[right-1] # put pivot on right\n",
" return self.theArray[right-1] # return median value\n",
"\n",
" def insertionSort(self,left,right):\n",
" i = 0\n",
" out = 0 # sorted on left of out\n",
" for out in range(left+1,right+1):\n",
" temp = self.theArray[out] # remove marked item\n",
" i = out # start shifts at out\n",
" # until one is smaller,\n",
" while(i >left and self.theArray[i-1] >= temp):\n",
" self.theArray[i] = self.theArray[i-1] # shift item to right\n",
" i -= 1 # go left one position\n",
" self.theArray[i] = temp # insert marked item\n",
"\n",
"maxSize = 16 # array size\n",
"arr = ArrayIns(maxSize) # create array\n",
"import random\n",
"for j in range(maxSize): # fill array with\n",
" # random numbers\n",
" n = int(random.random()*99)\n",
" arr.insert(n)\n",
"arr.display() # display items\n",
"arr.quickSort() # quicksort them\n",
"arr.display() # display them again"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"A= 32 49 43 84 84 76 63 70 37 50 13 46 46 19 60 72 \n",
"A= 13 19 32 32 37 43 46 49 50 60 63 70 70 76 84 84 \n"
]
}
],
"prompt_number": 5
},
{
"cell_type": "code",
"collapsed": false,
"input": [],
"language": "python",
"metadata": {},
"outputs": []
}
],
"metadata": {}
}
]
}