CODEWITHSUNDEEP
pythonalgorithminsertion-sort
Melkor
Melkor

Reputation: 799

Insertion sort doesn't sort

I have attempted to create an insertion sort in python, however the list returned is not sorted. What is the problem with my code?

Argument given: [3, 2, 1, 4, 5, 8, 7, 9, 6]

Result: 2 1 3 6 4 7 5 8 9

Python code:

def insertion_sort(mylist):
    sorted_list = []
    for i in mylist:
        posfound = 0 #defaults to 0
        for j in range(len(sorted_list)):
            if sorted_list[j] > i:
                sorted_list.insert(j-1, i) #put the number in before element 'j'
                posfound = 1 #if you found the correct position in the list set to 1
                break
        if posfound == 0: #if you can't find a place in the list
            sorted_list.insert(len(sorted_list), i) #put number at the end of the list
    return sorted_list

Upvotes: 2

Views: 175

Answers (3)

PM 2Ring
PM 2Ring

Reputation: 55499

As Efferalgan & tzaman have mentioned your core problem is due to an off-by-one error. To catch these sorts of errors it's useful to print i, j and sorted_list on each loop iteration to make sure they contain what you think they contain.

Here are a few versions of your algorithm. First, a repaired version of your code that fixes the off-by-one error; it also implements Efferalgan's suggestion of using .append if an insertion position isn't found.

def insertion_sort(mylist):
    sorted_list = []
    for i in mylist:
        posfound = 0 #defaults to 0
        for j in range(len(sorted_list)):
            if sorted_list[j] > i:
                sorted_list.insert(j, i) #put the number in before element 'j'
                posfound = 1 #if you found the correct position in the list set to 1
                break
        if posfound == 0: #if you can't find a place in the list
            sorted_list.append(i) #put number at the end of the list
    return sorted_list

Here's a slightly improved version that uses an else clause on the loop instead of the posfound flag; it also uses slice assignment to do the insertion.

def insertion_sort(mylist):
    sorted_list = []
    for i in mylist:
        for j in range(len(sorted_list)):
            if sorted_list[j] > i:
                sorted_list[j:j] = [i]
                break
        else: #if you can't find a place in the list
            sorted_list.append(i) #put number at the end of the list
    return sorted_list

Finally, a version that uses enumerate to get the indices and items in sorted_list rather than a simple range loop.

def insertion_sort(mylist):
    sorted_list = []
    for u in mylist:
        for j, v in enumerate(sorted_list):
            if v > u:
                sorted_list[j:j] = [u]
                break
        else: #if you can't find a place in the list
            sorted_list.append(u) #put number at the end of the list
    return sorted_list

Upvotes: 2

Efferalgan
Efferalgan

Reputation: 1701

As often, it was a off-by-one error, the code below is fixed. I also made some parts a bit prettier.

def insertion_sort(mylist):
    sorted_list = []
    for i in mylist:
        for index, j in enumerate(sorted_list):
            if j > i:
                sorted_list.insert(index, i) #put the number in before element 'j'
                break
        else:
            sorted_list.append(i) #put number at the end of the list
    return sorted_list

Upvotes: 1

tzaman
tzaman

Reputation: 47850

You need to change sorted_list.insert(j-1, i) to be sorted_list.insert(j, i) to insert before position j.

insert(j-1, ..) will insert before the previous element, and in the case where j=0 it'll wrap around and insert before the last element.

The Python data structures tutorial may be useful.

Upvotes: 4

Related Questions