def insertion_sort(L):
for i in range(1,len(L)):
x = i
while x > 0 and L[x-1] >= L[x]:
x -= 1
value = L[i]
del L[i]
L.insert(x,value)
a = [5,2,6,3,1,8]
print "Before: ", a
insertion_sort(a)
print "After: ", a
For some reason the list is not sorted properly. I can't find the mistake here.
In fourth line it should be:
while x > 0 and L[x-1] >= L[i]:
Instead of
while x > 0 and L[x-1] >= L[x]:
From Wikipedia:
for i ← 1 to length(A) - 1
j ← i
while j > 0 and A[j-1] > A[j]
swap A[j] and A[j-1]
j ← j - 1
end while
end for
To translate into Python:
def insertion_sort(A):
for i in range(1, len(A)):
j = i
while j > 0 and A[j-1] > A[j]:
swap(A, j, j-1)
j = j - 1
def swap(A, f, t):
A[t], A[f] = A[f], A[t]
a = [5,2,6,3,1,8]
print "Before: ", a
insertion_sort(a)
print "After: ", a
Try to this..
def insertion_sort(L):
for i in range(1, len(L)):
val = L[i]
x = i - 1
while (x >= 0) and (L[x] > val):
L[x + 1] = L[x]
x = x - 1
L[x + 1] = val
a = [5, 2, 6, 3, 1, 8]
print "Before: ", a
insertion_sort(a)
print "After: ", a
