{
 "metadata": {
  "name": "",
  "signature": "sha256:3d75fa922b384c8005ae3c49ad4b92cedee585c19d876f3d1612e2a824146ea0"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "heading",
     "level": 1,
     "metadata": {},
     "source": [
      "Chapter 3 : Simple Sorting"
     ]
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "Example 3.1  Page No : 85"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      " \n",
      "\n",
      "class ArrayBub:\n",
      "    def __init__(self,m):\n",
      "        self.a = []\n",
      "        self.nElems = 0\n",
      "    \n",
      "    def insert(self,value):\n",
      "        # put element into array\n",
      "        self.a.append(value)\n",
      "        self.nElems += 1\n",
      "\n",
      "    def display(self):\n",
      "        # displays array contents\n",
      "        for j in range(self.nElems):\n",
      "            print self.a[j] ,\n",
      "        print ''\n",
      "\n",
      "    def bubbleSort(self):\n",
      "        out = self.nElems - 1\n",
      "        while out > 1 :\n",
      "            for i in range(out):        \n",
      "                if( self.a[i] > self.a[i+1] ):\n",
      "                    self.a[i],self.a[i+1] = self.a[i+1],self.a[i]                        \n",
      "            out -= 1\n",
      "\n",
      "maxSize = 100 # array size\n",
      "arr = ArrayBub(maxSize) # create the array\n",
      "arr.insert(77) # insert 10 items\n",
      "arr.insert(99) \n",
      "arr.insert(44) \n",
      "arr.insert(55) \n",
      "arr.insert(22) \n",
      "arr.insert(88) \n",
      "arr.insert(11) \n",
      "arr.insert(00) \n",
      "arr.insert(66) \n",
      "arr.insert(33) \n",
      "arr.display() # display items\n",
      "arr.bubbleSort() # bubble sort them\n",
      "arr.display()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "77 99 44 55 22 88 11 0 66 33 \n",
        "0 11 22 33 44 55 66 77 88 99 \n"
       ]
      }
     ],
     "prompt_number": 5
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "Example 3.2  Page No : 93"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      " \n",
      "class ArraySel:\n",
      "    def __init__(self,m):\n",
      "        self.a = []\n",
      "        self.nElems = 0\n",
      "    \n",
      "    def insert(self,value):\n",
      "        # put element into array\n",
      "        self.a.append(value)\n",
      "        self.nElems += 1\n",
      "\n",
      "    def display(self):\n",
      "        # displays array contents\n",
      "        for j in range(self.nElems):\n",
      "            print self.a[j] ,\n",
      "        print ''\n",
      "\n",
      "    def selectionSort(self):\n",
      "        for out in range(self.nElems-1):\n",
      "            for i in range(out,self.nElems):        \n",
      "                if( self.a[i] < self.a[out] ):\n",
      "                    self.a[i],self.a[out] = self.a[out],self.a[i]                        \n",
      "\n",
      "maxSize = 100 # array size\n",
      "arr = ArraySel(maxSize) # create the array\n",
      "arr.insert(77) # insert 10 items\n",
      "arr.insert(99) \n",
      "arr.insert(44) \n",
      "arr.insert(55) \n",
      "arr.insert(22) \n",
      "arr.insert(88) \n",
      "arr.insert(11) \n",
      "arr.insert(00) \n",
      "arr.insert(66) \n",
      "arr.insert(33) \n",
      "arr.display() # display items\n",
      "arr.selectionSort() # bubble sort them\n",
      "arr.display()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "77 99 44 55 22 88 11 0 66 33 \n",
        "0 11 22 33 44 55 66 77 88 99 \n"
       ]
      }
     ],
     "prompt_number": 2
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "Example 3.3 Page No : 101"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      " \n",
      "class ArrayIns:\n",
      "    def __init__(self,m):\n",
      "        self.a = [] # create the array\n",
      "        self.nElems = 0 # no items yet\n",
      "\n",
      "    def insert(self,value): # put element into array\n",
      "        self.a.append(value) # insert it\n",
      "        self.nElems += 1 # increment size\n",
      "\n",
      "    def display(self): # displays array contents\n",
      "        for j in range(self.nElems): # for each element,\n",
      "            print self.a[j] ,  # display it\n",
      "        print ''\n",
      "\n",
      "    def insertionSort(self):\n",
      "        for out in range(self.nElems):\n",
      "            temp = self.a[out]\n",
      "            i = out\n",
      "            while (i>0 and self.a[i-1] >= temp):\n",
      "                self.a[i] = self.a[i-1]\n",
      "                i -= 1\n",
      "            self.a[i] = temp\n",
      "\n",
      "maxSize = 100 # array size\n",
      "arr = ArrayIns(maxSize) # create the array\n",
      "arr.insert(77) # insert 10 items\n",
      "arr.insert(99) \n",
      "arr.insert(44) \n",
      "arr.insert(55) \n",
      "arr.insert(22) \n",
      "arr.insert(88) \n",
      "arr.insert(11) \n",
      "arr.insert(00) \n",
      "arr.insert(66) \n",
      "arr.insert(33) \n",
      "arr.display() # display items\n",
      "arr.insertionSort() # insertion-sort them\n",
      "arr.display()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "77 99 44 55 22 88 11 0 66 33 \n",
        "0 11 22 33 44 55 66 77 88 99 \n"
       ]
      }
     ],
     "prompt_number": 3
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "Example 3.4 Page No : 104"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      " \n",
      "class Person:\n",
      "    def __init__(self,last,first,a):\n",
      "        # constructor\n",
      "        self.lastName = last\n",
      "        self.firstName = first\n",
      "        self.age = a\n",
      "\n",
      "    def displayPerson(self):\n",
      "        print 'Last name: ', self.lastName , ', First name: ',self.firstName , ', Age: ' , self.age\n",
      "\n",
      "    def getLast(self): # get last name\n",
      "        return self.lastName \n",
      "\n",
      "class ArrayInOb:\n",
      "    def __init__(self,m):\n",
      "        self.a = [] # create the array\n",
      "        self.nElems = 0 # no items yet\n",
      "    \n",
      "    def insert(self,last,first,age):\n",
      "        self.a.append(Person(last, first, age))\n",
      "        self.nElems += 1 # increment size\n",
      "\n",
      "    def display(self): # displays array contents\n",
      "        for j in range(self.nElems): # for each element,\n",
      "            self.a[j].displayPerson() # display it\n",
      "        print ''\n",
      "\n",
      "    def insertionSort(self):\n",
      "        for out in range(1,self.nElems):\n",
      "            temp = self.a[out]\n",
      "            i = out\n",
      "            while(i>0 and self.a[i-1].getLast() > temp.getLast()):\n",
      "                self.a[i] = self.a[i-1] # shift item to the right\n",
      "                i -= 1 # go left one position\n",
      "            self.a[i] = temp\n",
      "maxSize = 100 # array size\n",
      "arr = ArrayInOb(maxSize) # create the array\n",
      "arr.insert('Evans', 'Patty', 24)\n",
      "arr.insert('Smith', 'Doc', 59)\n",
      "arr.insert('Smith', 'Lorraine', 37)\n",
      "arr.insert('Smith', 'Paul', 37)\n",
      "arr.insert('Yee', 'Tom', 43)\n",
      "arr.insert('Hashimoto', 'Sato', 21)\n",
      "arr.insert('Stimson', 'Henry', 29)\n",
      "arr.insert('Velasquez', 'Jose', 72)\n",
      "arr.insert('Vang', 'Minh', 22)\n",
      "arr.insert('Creswell', 'Lucinda', 18)\n",
      "print 'Before sorting:'\n",
      "arr.display() # display items\n",
      "arr.insertionSort() # insertion-sort them\n",
      "print 'After sorting:'\n",
      "arr.display() # display them again"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Before sorting:\n",
        "Last name:  Evans , First name:  Patty , Age:  24\n",
        "Last name:  Smith , First name:  Doc , Age:  59\n",
        "Last name:  Smith , First name:  Lorraine , Age:  37\n",
        "Last name:  Smith , First name:  Paul , Age:  37\n",
        "Last name:  Yee , First name:  Tom , Age:  43\n",
        "Last name:  Hashimoto , First name:  Sato , Age:  21\n",
        "Last name:  Stimson , First name:  Henry , Age:  29\n",
        "Last name:  Velasquez , First name:  Jose , Age:  72\n",
        "Last name:  Vang , First name:  Minh , Age:  22\n",
        "Last name:  Creswell , First name:  Lucinda , Age:  18\n",
        "\n",
        "After sorting:\n",
        "Last name:  Creswell , First name:  Lucinda , Age:  18\n",
        "Last name:  Evans , First name:  Patty , Age:  24\n",
        "Last name:  Hashimoto , First name:  Sato , Age:  21\n",
        "Last name:  Smith , First name:  Doc , Age:  59\n",
        "Last name:  Smith , First name:  Lorraine , Age:  37\n",
        "Last name:  Smith , First name:  Paul , Age:  37\n",
        "Last name:  Stimson , First name:  Henry , Age:  29\n",
        "Last name:  Vang , First name:  Minh , Age:  22\n",
        "Last name:  Velasquez , First name:  Jose , Age:  72\n",
        "Last name:  Yee , First name:  Tom , Age:  43\n",
        "\n"
       ]
      }
     ],
     "prompt_number": 4
    }
   ],
   "metadata": {}
  }
 ]
}