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)

• David Harkness: This acts more like bubble sort in that it swaps more elements than necessary. The inner loop should not put the sorted sublist out of order. You need to run the inner loop in reverse and move the ith element toward the front of the sorted list--swapping each time with the next element closer to the front--until it finds its spot.

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.