#=======================================================================
# Author: Isai Damier
# Title: Insertionsort
# Project: geekviewpoint
# Package: algorithms
#
# Statement:
# Given a disordered list of integers (or any other items),
# rearrange the integers in natural order.
#
# Sample Input: [8,5,3,1,9,6,0,7,4,2,5]
# Sample Output: [0,1,2,3,4,5,5,6,7,8,9]
#
# Time Complexity of Solution:
# Best O(n); Average O(n^2); Worst O(n^2).
#
# Approach:
# Insertion sort is good for collections that are very small
# or nearly sorted. Otherwise it's not a good sorting algorithm:
# it moves data around too much. Each time an insertion is made,
# all elements in a greater position are shifted.
#=======================================================================
def insertionsort( aList ):
for i in range( 1, len( aList ) ):
tmp = aList[i]
k = i
while k > 0 and tmp < aList[k - 1]:
aList[k] = aList[k - 1]
k -= 1
aList[k] = tmp
import unittest
from algorithms import sorting
class Test( unittest.TestCase ):
def testInsertionsort( self ):
A = [8, 5, 3, 1, 9, 6, 0, 7, 4, 2, 5]
sorting.insertionsort( A )
for i in range( 1, len( A ) ):
if A[i - 1] > A[i]:
self.fail( "insertionsort method fails." )
