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?
As this looks like a school assignment, I'm answering with a bunch of questions for the student of algorithms to ponder:
a?With suggestions from my peer reviewers I have corrected my code and posting my corrected solution.
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]
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])
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)
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
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")
'Please give valid input' is too generic. How about:
if not a:
raise ValueError("Argument 'a' must be a non-empty `list` object.")
current = current + 1 can be shortened using the in-place add operator (__iadd__() ↔ +=):
current += 1
There is really no good excuse to use Python 2 these days.
