CODEWITHSUNDEEP
python
Dhruv Mullick
Dhruv Mullick

Reputation: 561

Implementing Insertion Sort in Python with For Loops only

I tried implementing Insertion sort with for loops only and wrote the following code:

def isort(L):    #implementation with a for loop
    for i in range(1,len(L)):
        small = L[i]
        M = range(i)
        M.reverse()
        for j in M:
            if small<L[j]:
                L[j+1]=L[j]
            else:
                break
        L[j+1] = small
    return L

L = [5,4,3,2,1]
M = isort(L)
print M

This gives the output [5,1,2,3,4]. Can someone please point out where I am making a mistake

Upvotes: 1

Views: 3447

Answers (4)

San Neupane
San Neupane

Reputation: 1

if __name__ == "__main__":
    n = int(input("How many numbers ?\t"))    
    nums = [int(x) for x in input("Enter {} numbers\t".format(n)).split()]    

    for i in range(1,n):        
        val = nums[i]  
        for j in range(i-1,-2,-1):           
            if j < 0 : break
            if nums[j] > val:
                nums[j+1] = nums[j]
            else:                                
                break
        nums[j+1] = val

    for num in nums:
        print(num,end=' ')

    print()

Upvotes: 0

Joshna Gunturu
Joshna Gunturu

Reputation: 161

This is little tricky :

I took the inner loop range function as range(j, -2, -1) , so the inner loop always breaks at one position ahead, so the last statement arr[j + 1] = key works perfectly

arr = [5, 4, 3, 2, 1]
for i in range(1, len(arr)):
    j = i - 1
    key = arr[i]
    for j in range(j, -2, -1):
        if j < 0 or key >= arr[j]:
            break
        else:
            arr[j + 1] = arr[j]

    arr[j + 1] = key

Upvotes: 0

anon582847382
anon582847382

Reputation: 20361

Change (the fix shown in the question is easy, the one-off error was caused by one little +1 :)):

L[j+1] = small

To:

L[j] = small

Testing:

>>> isort([5, 4, 3, 2, 1])
[1, 2, 3, 4, 5]

However, there are some other things with your code, as illustrated- it will not work alot of the time. With a fair few tweaks, we can get it to work:

def isort(L):
    for i in range(1,len(L)):
        small = L[i]
        M = range(-1, i)
        M.reverse()
        for j in M:
            if j>=0 and small<L[j]:
                L[j+1]=L[j]
            else:
                break
        L[j+1] = small
    return L

Testing:

>>> isort([4, 5, 3, 2, 1])
[1, 2, 3, 4, 5]

Upvotes: 4

tmrlvi
tmrlvi

Reputation: 2361

The post condition for the inner loop is that j is pointing for the first value that is smaller than small (this is achieved by the break call). However, the loop naturally exists when j=0, therefore in every last inner iteration, the condition is not what you'd expect.

To fix it, I suggest initializing M from -1:

M = range(-1, i)

But then, you have to check as well that j is positive (to avoid making changes you don't want to):

if j>=0 and small<L[j]:
    L[j+1]=L[j]

Upvotes: 3

Related Questions