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