{
 "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": {}
  }
 ]
}