- "name": "ch7"

- "source": "Chapter 7 : Advanced Sorting "

- "source": "Example 7.1 Page no : 321"

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

- "text": "A= 35 47 88 24 10 98 14 75 97 38 \nA= 10 14 24 35 38 47 75 88 97 98 \n"

- "source": "Example 7.2 Page No 327"

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

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

- "source": "Example 7.3 Page no : 337"

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

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

- "source": "Example 7.4 Page No : 347"

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

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

- "source": "Example 7.5 Page No : 351"

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

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

- "input": "",