def insertionSort():
for out in range(1, nElems): #out is dividing line
temp = v[out] #remove marked item
#using In as in is reserved in Python
In = out #start shifts at out
while (In > 0) and (v[In-1] > temp): #until one is smaller
v[In] = v[In -1] #shift item to right
In -= In-1#go left one position
v[In] = temp #insert marked item
#end for
#end insertionSort()
#demonstrates insertion sort
class ArrayIns:
def __init__(self): #special method to create objects
#with instances customized to a specific initial state
#since private instance variables don't exist in Python,
#hence using a convention: name prefixed with an underscore, to treat them as non-public part
self._v = [] #list _v
def insert(self, value): #put element into array
self._v.append(value) #insert it
def display(self): #displays array contents
print self._v #display it
def insertionSort(self):
for out in range(1, len(self._v)): #out is dividing line
temp = self._v[out] #remove marked item
#using In as in is reserved in Python
In = out #start shifts at out
while (In > 0) and (self._v[In-1] > temp): #until one is smaller
self._v[In] = self._v[In -1] #shift item to right
In -= 1#go left one position
self._v[In] = temp #insert marked item
#end for
#end insertionSort()
#end class ArrayIns
arr = ArrayIns() #create 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() #display them again
#end
#demonstrates sorting objects (uses insertion sort)
class Person:
"""A simple person class"""
def __init__(self, last, first, a): #special method to create objects
#with instances customized to a specific initial state
#since private instance variables don't exist in Python,
#hence using a convention: name prefixed with an underscore, to treat them as non-public part
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 #get last name
#end class Person
class ArrayInOb:
#since private instance variables don't exist in Python,
#hence using a convention: name prefixed with an underscore, to treat them as non-public part
def __init__(self):
self._v = [] #list to store Person type items
def insert(self, last, first, age): #put person into array
self._v.append(Person(last, first, age))
def display(self): #displays array contents
for j in self._v: #for each element,
j.displayPerson() #display it
def insertionSort(self):
for out in range(1, len(self._v)):
temp = self._v[out] #out is dividing line
#using In as in is reserved in Python
In = out #start shifting at out
while (In > 0) and (self._v[In-1].getLast() > temp.getLast()): #until smaller one found,
self._v[In] = self._v[In -1] #shift item to the right
In -= 1#go left one position
self._v[In] = temp #insert marked item
#end for
#end insertionSort()
#end class ArrayInOb
arr = ArrayInOb() #create 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
#end