37 lines
856 B
Python
37 lines
856 B
Python
#---------------------------------------
|
|
# 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) |