Insertion Sort Python

Question

I have implemented insertion sort in python and was wondering how to determine the complexity of the algorithm. Is this an inefficient way of implementing insertion sort? To me, this seems like the most readable algorithm.

import random as rand
source = [3,1,0,10,20,2,1]
target = []
while len(source)!=0:
 if len(target) ==0:
  target.append(source[0])
  source.pop(0)
 element = source.pop(0)
 if(element <= target[0]):
  target.reverse()
  target.append(element)
  target.reverse()
 elif element > target[len(target)-1]:
  target.append(element) 
 else:
  for i in range(0,len(target)-1):
   if element >= target[i] and element <= target[i+1]:
    target.insert(i+1,element)
    break
print target

Not your question, but since you've mentioned "readability": in python, while len(source)!=0 is equivalent to while source if you know that source is a list or string, etc. Also, if len(target) == 0 can be if not target — askewchan
– askewchan, Commented Mar 5, 2013 at 21:10
Reading PEP-8 is also recommended. Indent by 4 spaces, for example. — Tim Pietzcker
– Tim Pietzcker, Commented Mar 5, 2013 at 21:18
you only intend for the first if statement inside your while loop to be called once. So move it out of the loop - place it before the loop. As it is now, given a one element list, your function will try to pop an element from it - twice. — Will Ness
– Will Ness, Commented Mar 5, 2013 at 21:30

Neil · Accepted Answer · 2013-03-06 01:38:11Z

2

Instead of:

target.reverse()
target.append(element)
target.reverse()

try:

target.insert(0, element)

Also, maybe use a for loop, instead of a while loop, to avoid source.pop()?:

for value in source:
  ...

In the final else block, the first part of the if test is redundant:

else:
   for i in range(0,len(target)-1):
     if element >= target[i] and element <= target[i+1]:
        target.insert(i+1,element)
        break

Since the list is already sorted, as soon as you find an element larger than the one you're inserting, you've found the insertion location.

edited Mar 6, 2013 at 1:38

answered Mar 5, 2013 at 21:26

Neil

2,4381 gold badge21 silver badges29 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Will Ness Over a year ago

inserting 10 into [1,4,17], without the second part of that test, 10 would be inserted after 1. So the 2nd part of that test is needed.

Neil Over a year ago

Good point, @WillNess. It's the first part that is redundant. My note after the comment block was my main point. I updated the answer.

Radio- · Accepted Answer · 2013-03-05 22:46:48Z

1

I would say it is rather inefficient. How can you tell? Your approach creates a second array, but you don't need one in a selection sort. You use a lot of operations -- selection sort requires lookups and exchanges, but you have lookups, appends, pops, inserts, and reverses. So you know that you can probably do better.

answered Mar 5, 2013 at 22:46

Radio-

3,18123 silver badges22 bronze badges

Comments

kasavbere · Accepted Answer · 2013-03-06 00:50:51Z

1

def insertionsort( aList ):
  for i in range( 1, len( aList ) ):
    tmp = aList[i]
    k = i
    while k > 0 and tmp < aList[k - 1]:
        aList[k] = aList[k - 1]
        k -= 1
    aList[k] = tmp

This code is taken from geekviewpoint.com. Clearly it's a O(n^2) algorithm since it's using two loops. If the input is already sorted, however, then it's O(n) since the while-loop would then always be skipped due to tmp < aList[k - 1] failing.

answered Mar 6, 2013 at 0:50

kasavbere

6,02314 gold badges52 silver badges73 bronze badges

Collectives™ on Stack Overflow

Insertion Sort Python

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related