CODEWITHSUNDEEP
pythonalgorithmsorting
user3141977
user3141977

Reputation:

Insertion sort algorithm not working

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.

Upvotes: 0

Views: 64

Answers (3)

Haresh Shyara
Haresh Shyara

Reputation: 1886

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

Upvotes: 0

Steve Wilhelm
Steve Wilhelm

Reputation: 6270

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

Upvotes: 0

Ashwani
Ashwani

Reputation: 2052

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]:

Upvotes: 1

Related Questions