Implement Insertion sort in Python

Question

Task : Implement Insertion Sort in Python.

def insert_sort(a):
""" Fuction to sort a given list a """
 if len(a)==0:
 print "Please give valid input"
 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?

• Anshul Goyal: 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?

Answer 1

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?

Answer 2

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])
   

Answer 3

Don't confuse docstrings and comments.

""" 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)

Answer 4

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

   if not a:
    print "Please give valid input"
   

   ... 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:
    raise ValueError("Please give valid input")
   

3. 'Please give valid input' is too generic. How about:

   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
   

5. There is really no good excuse to use Python 2 these days.