#---------------------------------------

# Insertion Sort

#---------------------------------------

# not optimized, equiv to while version below, but uses for loop

def insertion_sort1(A):

for i in range(1, len(A)):

for j in range(i-1, -1, -1):

if A[j] > A[j+1]:

A[j], A[j+1] = A[j+1], A[j]

else:

break

# not optimized, equiv to break version, but uses while loop

def insertion_sort2(A):

for i in range(1, len(A)):

j = i-1

while A[j] > A[j+1] and j >= 0:

A[j], A[j+1] = A[j+1], A[j]

j -= 1

# optimized - shifts instead of swapping

def insertion_sort3(A):

for i in range(1, len(A)):

curNum = A[i]

k = 0

for j in range(i-1, -2, -1):

k = j

if A[j] > curNum:

A[j+1] = A[j]

else:

break

A[k+1] = curNum

A = [5,9,1,2,4,8,6,3,7]

print(A)

insertion_sort1(A)

print(A)