Khan inspired Insertion Sort

Question

I just watched a Khan Academy video on Insertion Sort and I've tried to write an implementation in Python. Please suggest corrections or improvements on this program:

unsorted_list=[45,99,1,-22,7,3,294,10,36]

def insertion_sort(unsorted):
    for i in range(1,len(unsorted)):
        for j in range(i):
            if unsorted[i]<unsorted[j]:
                temp = unsorted[j]    
                unsorted[j]=unsorted[i]
                unsorted[i]=temp

    return unsorted 

print insertion_sort(unsorted_list)

Answer 1

I wouldn't call your implementation insertion sort as it's sorting in place using swaps, which as David pointed out makes it look more like a bubble sort. An insertion sort sorts by building up a new list and inserting items into the proper place. A very crude first pass at an insertion sort might look like:

def insertion_sort(unsorted_list):
    result = []
    for n in unsorted_list:
        inserted = False
        for i in range(len(result)):
            if n < result[i]:
                result.insert(i, n)
                inserted = True
                break
        if not inserted:
            result.append(n)
    return result

This could be greatly improved for larger data sets by making the inner search take advantage of the fact that s is sorted and doing a binary search for the insertion point. Of course, this being Python, the whole mess could be optimized to sorted(unsorted_list). ;)

Answer 2

And swapping in Python can be performed less verbose way:

unsorted[i], unsorted[j] = unsorted[j], unsorted[i]

Answer 3

The name unsorted for a list which eventually becomes sorted is terrible.

Call it the_list or something else. But don't give it a name which -- at the end of the insertion_sort function will be untrue. Give it a name which will always be true.