6
\$\begingroup\$

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)
\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – David Harkness Jul 3 '11 at 12:15
6
\$\begingroup\$

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). ;)

|improve this answer|||||
\$\endgroup\$
5
\$\begingroup\$

And swapping in Python can be performed less verbose way:

unsorted[i], unsorted[j] = unsorted[j], unsorted[i]
|improve this answer|||||
\$\endgroup\$
2
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.