1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
|
{
"metadata": {
"name": "ch7"
},
"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": "'''\nExample 7.1\ndemonstrates shell sort\n'''\n\nclass 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\nmaxSize = 10 # array size\narr = ArraySh(maxSize) # create the array\nimport random\nfor j in range(maxSize): # fill array with\n # random numbers\n n = int(random.random()*99)\n arr.insert(n)\n\narr.display() # display unsorted array\narr.shellSort() # shell sort the array\narr.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 \nA= 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": "'''\nexample 7.2\ndemonstrates partitioning an array\n'''\nclass 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\nmaxSize = 16 # array size\narr = ArrayPar(maxSize) # create the array\nimport random\nfor j in range(maxSize): # fill array with\n # random numbers\n n = int(random.random()*199)\n arr.insert(n)\narr.display() # display unsorted array\npivot = 99 # pivot value\nprint \"Pivot is \", pivot ,\nsize = arr.size() # partition array\npartDex = arr.partitionIt(0, size-1, pivot)\nprint \", Partition is at index \" , partDex \narr.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 \nPivot is 99 , Partition is at index 9\nA= 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": "'''\nexample 7.3\ndemonstrates simple version of quick sort\n'''\nclass 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\nmaxSize = 16 # array size\narr = ArrayIns(maxSize) # create array\nimport random\nfor j in range(maxSize): # fill array with\n # random numbers\n n = int(random.random()*99)\n arr.insert(n)\narr.display() # display items\narr.quickSort() # quicksort them\narr.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 \nA= 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": "'''\nexample 7.4\ndemonstrates quick sort with median-of-three partitioning\n'''\nclass 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\nmaxSize = 16 # array size\narr = ArrayIns(maxSize) # create array\nimport random\nfor j in range(maxSize): # fill array with\n # random numbers\n n = int(random.random()*99)\n arr.insert(n)\narr.display() # display items\narr.quickSort() # quicksort them\narr.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 \nA= 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": "'''\nexample 7.5\ndemonstrates quick sort uses insertion sort for cleanup\n'''\nclass 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\nmaxSize = 16 # array size\narr = ArrayIns(maxSize) # create array\nimport random\nfor j in range(maxSize): # fill array with\n # random numbers\n n = int(random.random()*99)\n arr.insert(n)\narr.display() # display items\narr.quickSort() # quicksort them\narr.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 \nA= 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": {}
}
]
}
|
