HiveBrain v1.2.0
Get Started
← Back to all entries
snippetpythonMinor

Khan inspired Insertion Sort

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
khaninsertionsortinspired

Problem

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)

Solution

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

Code Snippets

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

Context

StackExchange Code Review Q#3264, answer score: 6

Revisions (0)

No revisions yet.