# Implement Insertion sort in Python

Task : Implement Insertion Sort in Python.

def insert_sort(a):
""" Fuction to sort a given list a """
if len(a)==0:
for i in range(1, len(a)):
current = 0
while current < i:
if a[i] < a[current]:
a[current], a[i]= a[i] , a[current]
current = current + 1
return a

print insert_sort([12,54,66,43,11,33,34,33,1,45])


How can this code be better?

• The implementation you are doing in the code is essentially a bubble sort.. calling it insert_sort doesn't make it insertion sort.. I would suggest you get the basics right before posting on the platform.. See codereview.stackexchange.com/help/how-to-ask and codereview.stackexchange.com/help/on-topic and try to answer for yourself - does the code work as intended? Commented Apr 25, 2018 at 21:10

As this looks like a school assignment, I'm answering with a bunch of questions for the student of algorithms to ponder:

• Why do you think an empty list should be invalid input?
• Could you think of a more descriptive name for the parameter than a?
• You have a loop from 1 to length of array. This looks like an off by one error. Normally one would loop over indexes of 0..length-1. Could this loop be improved so it doesn't look suspicious?
• Why are you using an outer for-loop and an inner while loop? Why not not in reverse? Why not use the same looping construct for both?
• As this is an insertions sort, how do you perform an insertion to Python list, and where in this code is that insertion used?
• How can you make sure that this solution really works? Could you write an automated test to check that it's correctly sorting various inputs?

With suggestions from my peer reviewers I have corrected my code and posting my corrected solution.

1. The code in question does not do insertion sort, the while loop here compares two elements in the list and swaps them if the current element is found smaller than the element in sorted sublist. For example to insert 43 in sorted sublist the element is swapped with 54

[12, 54, 66, 43, 11, 33, 34, 33, 1, 45]
[12, 43, 66, 54, 11, 33, 34, 33, 1, 45]


But ideally as per insertion sort the elements to the left of 43 should be shifted one step right to insert it in the sorted sub list

[12, 43, 54, 66, 11, 33, 34, 33, 1, 45]

2. A better working solution for insertion sort can be this:

def insert_sort(alist):
""" Fuction to sort a given list a """

for i in range(0, len(alist)-1):
current = i+1
while current :
"""if the current number is lesser than the number on left than swap values"""
if alist[current] < alist[i]:
alist[current], alist[i] = alist[i], alist[current]
print alist
current = current - 1
i = i - 1

return alist

print insert_sort([12,54,66,43,11,33,34,33,1,45])


""" Fuction to sort a given list a """


Putting a string in your function like this stores it in the function as a docstring. It is intended so that people who want to use your code can find out what it is meant to do. They can check it with print(insert_sort.__doc__)

Including docstrings like this is good! For further conventions about how to use them, look here.

When you want to help people who want to read your code to understand it, you should use a comment. These start with # and don't need quotes.

# Current tracks which element we're comparing.


You shouldn't use strings as general purpose comments.

(Although if you have described what a function is for in a docstring, it is not necessary to repeat yourself in a comment)

1. In Python, the idiomatic way of checking if a container is empty, is to query its __bool__() method:

if not a:


... which returns False if the container is empty, and True otherwise. This also works for strings, for example:

>>> s1 = "Hello, World!"
>>> s2 = ""
>>> bool(s1)
True
>>> bool(s2)
False

2. Don't use print for error messages. If you want to warn the caller they passed an illegal value, raise a ValueError:

if not a:

if not a:
raise ValueError("Argument 'a' must be a non-empty list object.")

4. current = current + 1 can be shortened using the in-place add operator (__iadd__()+=):
current += 1