CODEWITHSUNDEEP
pythonsorting
Yarden
Yarden

Reputation: 679

insertion sort in python?

I wrote a code for insertion sort that now works great (yes, it's homework). But, before that code I wrote a different one that doesn't work and I just don't know why. Please help me understand...

This is my older code:

def insertion_sort(lst):
    if len(lst)==1:
        lst=lst
    else:
        for i in lst[1:]:
            if i==min(lst[0:lst.index(i)]):
                 lst.remove(i)
                 lst.insert(0, i)
    return lst

I do not need a new insertion sort, I already wrote one. I just need the explanation for why this specific code didn't work.

Upvotes: 1

Views: 271

Answers (1)

Xymostech
Xymostech

Reputation: 9850

The problem is that sometimes, even though i isn't the smallest of lst[0:lst.index(i)], it still needs to be moved downwards. So, for example, if lst[0:lst.index(i)] is [0, 1, 2, 4, 3], then even though the minimum is 0, you still need to move 3 down a place for insertion sort to work.

Upvotes: 1

Related Questions