# 5: The Insertion Sort¶

## Example 1: Page 94¶

In [1]:
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()


## Example 2: Page 96¶

In [2]:
#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

[77, 99, 44, 55, 22, 88, 11, 0, 66, 33]
[0, 11, 22, 33, 44, 55, 66, 77, 88, 99]


## Example 3: Page 98¶

In [1]:
#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

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