Chapter 3 : Simple Sorting

Example 3.1 Page No : 85

In [5]:
 

class ArrayBub:
    def __init__(self,m):
        self.a = []
        self.nElems = 0
    
    def insert(self,value):
        # put element into array
        self.a.append(value)
        self.nElems += 1

    def display(self):
        # displays array contents
        for j in range(self.nElems):
            print self.a[j] ,
        print ''

    def bubbleSort(self):
        out = self.nElems - 1
        while out > 1 :
            for i in range(out):        
                if( self.a[i] > self.a[i+1] ):
                    self.a[i],self.a[i+1] = self.a[i+1],self.a[i]                        
            out -= 1

maxSize = 100 # array size
arr = ArrayBub(maxSize) # create the array
arr.insert(77) # insert 10 items
arr.insert(99) 
arr.insert(44) 
arr.insert(55) 
arr.insert(22) 
arr.insert(88) 
arr.insert(11) 
arr.insert(00) 
arr.insert(66) 
arr.insert(33) 
arr.display() # display items
arr.bubbleSort() # bubble sort them
arr.display()

77 99 44 55 22 88 11 0 66 33 
0 11 22 33 44 55 66 77 88 99

Example 3.2 Page No : 93

In [2]:
 
class ArraySel:
    def __init__(self,m):
        self.a = []
        self.nElems = 0
    
    def insert(self,value):
        # put element into array
        self.a.append(value)
        self.nElems += 1

    def display(self):
        # displays array contents
        for j in range(self.nElems):
            print self.a[j] ,
        print ''

    def selectionSort(self):
        for out in range(self.nElems-1):
            for i in range(out,self.nElems):        
                if( self.a[i] < self.a[out] ):
                    self.a[i],self.a[out] = self.a[out],self.a[i]                        

maxSize = 100 # array size
arr = ArraySel(maxSize) # create the array
arr.insert(77) # insert 10 items
arr.insert(99) 
arr.insert(44) 
arr.insert(55) 
arr.insert(22) 
arr.insert(88) 
arr.insert(11) 
arr.insert(00) 
arr.insert(66) 
arr.insert(33) 
arr.display() # display items
arr.selectionSort() # bubble sort them
arr.display()

77 99 44 55 22 88 11 0 66 33 
0 11 22 33 44 55 66 77 88 99

Example 3.3 Page No : 101

In [3]:
 
class ArrayIns:
    def __init__(self,m):
        self.a = [] # create the array
        self.nElems = 0 # no items yet

    def insert(self,value): # put element into array
        self.a.append(value) # insert it
        self.nElems += 1 # increment size

    def display(self): # displays array contents
        for j in range(self.nElems): # for each element,
            print self.a[j] ,  # display it
        print ''

    def insertionSort(self):
        for out in range(self.nElems):
            temp = self.a[out]
            i = out
            while (i>0 and self.a[i-1] >= temp):
                self.a[i] = self.a[i-1]
                i -= 1
            self.a[i] = temp

maxSize = 100 # array size
arr = ArrayIns(maxSize) # create the array
arr.insert(77) # insert 10 items
arr.insert(99) 
arr.insert(44) 
arr.insert(55) 
arr.insert(22) 
arr.insert(88) 
arr.insert(11) 
arr.insert(00) 
arr.insert(66) 
arr.insert(33) 
arr.display() # display items
arr.insertionSort() # insertion-sort them
arr.display()

77 99 44 55 22 88 11 0 66 33 
0 11 22 33 44 55 66 77 88 99

Example 3.4 Page No : 104

In [4]:
 
class Person:
    def __init__(self,last,first,a):
        # constructor
        self.lastName = last
        self.firstName = first
        self.age = a

    def displayPerson(self):
        print 'Last name: ', self.lastName , ', First name: ',self.firstName , ', Age: ' , self.age

    def getLast(self): # get last name
        return self.lastName 

class ArrayInOb:
    def __init__(self,m):
        self.a = [] # create the array
        self.nElems = 0 # no items yet
    
    def insert(self,last,first,age):
        self.a.append(Person(last, first, age))
        self.nElems += 1 # increment size

    def display(self): # displays array contents
        for j in range(self.nElems): # for each element,
            self.a[j].displayPerson() # display it
        print ''

    def insertionSort(self):
        for out in range(1,self.nElems):
            temp = self.a[out]
            i = out
            while(i>0 and self.a[i-1].getLast() > temp.getLast()):
                self.a[i] = self.a[i-1] # shift item to the right
                i -= 1 # go left one position
            self.a[i] = temp
maxSize = 100 # array size
arr = ArrayInOb(maxSize) # create the array
arr.insert('Evans', 'Patty', 24)
arr.insert('Smith', 'Doc', 59)
arr.insert('Smith', 'Lorraine', 37)
arr.insert('Smith', 'Paul', 37)
arr.insert('Yee', 'Tom', 43)
arr.insert('Hashimoto', 'Sato', 21)
arr.insert('Stimson', 'Henry', 29)
arr.insert('Velasquez', 'Jose', 72)
arr.insert('Vang', 'Minh', 22)
arr.insert('Creswell', 'Lucinda', 18)
print 'Before sorting:'
arr.display() # display items
arr.insertionSort() # insertion-sort them
print 'After sorting:'
arr.display() # display them again

Before sorting:
Last name:  Evans , First name:  Patty , Age:  24
Last name:  Smith , First name:  Doc , Age:  59
Last name:  Smith , First name:  Lorraine , Age:  37
Last name:  Smith , First name:  Paul , Age:  37
Last name:  Yee , First name:  Tom , Age:  43
Last name:  Hashimoto , First name:  Sato , Age:  21
Last name:  Stimson , First name:  Henry , Age:  29
Last name:  Velasquez , First name:  Jose , Age:  72
Last name:  Vang , First name:  Minh , Age:  22
Last name:  Creswell , First name:  Lucinda , Age:  18

After sorting:
Last name:  Creswell , First name:  Lucinda , Age:  18
Last name:  Evans , First name:  Patty , Age:  24
Last name:  Hashimoto , First name:  Sato , Age:  21
Last name:  Smith , First name:  Doc , Age:  59
Last name:  Smith , First name:  Lorraine , Age:  37
Last name:  Smith , First name:  Paul , Age:  37
Last name:  Stimson , First name:  Henry , Age:  29
Last name:  Vang , First name:  Minh , Age:  22
Last name:  Velasquez , First name:  Jose , Age:  72
Last name:  Yee , First name:  Tom , Age:  43