snippetpythonMinor
Khan inspired Insertion Sort
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:
This could be greatly improved for larger data sets by making the inner search take advantage of the fact that
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 resultThis 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 resultContext
StackExchange Code Review Q#3264, answer score: 6
Revisions (0)
No revisions yet.