CODEWITHSUNDEEP
pythondebuggingsortinginsertion-sort
jaredad7
jaredad7

Reputation: 1058

Strange bug in insertion sort in python

I don't know if the language, data type, or my algorithm has something to do with it, but I get this strange bug with my insertion sort written in python. I was writing it in preparation for a potential exam question tomorrow, and it works, but it only seems to work for numbers >= 1. I will demonstrate the output given two different inputs:

#Insertion Sort
#Has some weird bug; only works for numbers >= 1.
def insertion(arr):
    for i in range(1,len(arr)):
        m = arr[i]
        for x in range(i-1,-1,-1):
            if(arr[x] > m):
                arr[x+1] = arr[x]
            else:
                arr[x+1] = m
                break
    return arr

The following is a set of inputs given to the function:

l1 = [1,3,7,2,5,8,4,6]
l2 = [1.1,3.7,7.0,2.5,5.1,8.3,4.0,7.9,6.0]
l3 = [1,3,7,2,5,8,0,4,6]
l4 = [1.1,3.7,7.0,2.5,5.1,8.3,4.0,7.9,6.0,0.3]

The following is a list of outputs with respect to the above inputs

n1 = [1, 2, 3, 4, 5, 6, 7, 8]
n2 = [1.1, 2.5, 3.7, 4.0, 5.1, 6.0, 7.0, 7.9, 8.3]
n3 = [1, 1, 2, 3, 4, 5, 6, 7, 8]
n4 = [1.1, 1.1, 2.5, 3.7, 4.0, 5.1, 6.0, 7.0, 7.9, 8.3]

It seems that the sort function will move values < 1 all the way down to the beginning, but then replaces them with the lowest value in the list. I thought this was a very strange bug, but don't really have time right now to work on figuring it out (finals begin next week, as we are on the quarter system). I thought perhaps someone here would like to work on solving it. It may simply be an error in my logic, but I find it strange that it works perfectly for all values 1 or greater.

Upvotes: 0

Views: 189

Answers (1)

Amit Kumar Gupta
Amit Kumar Gupta

Reputation: 18567

The problem is if m is smaller than every element in the array arr before it, you never set arr[0] = m. If the arr[x] > m case always holds true, then you never set any entry in arr to m. So you'll get all the way to the front, copy the first element into the second position (with arr[x+1] = arr[x] when x is 0), but never actually insert m at the 0-th position with arr[0] = m. One (perhaps unusual) way to do this is to use Python's for... else construction, where the else case gets called if you never break out of the for loop:

def insertion(arr):
    for i in range(1,len(arr)):
        m = arr[i]
        for x in range(i-1,-1,-1):
            if(arr[x] > m):
                arr[x+1] = arr[x]
            else:
                arr[x+1] = m
                break
        else:
            arr[0] = m
    return arr

Upvotes: 1

Related Questions