CODEWITHSUNDEEP
pythonalgorithmsortinginsertion-sort
lord12
lord12

Reputation: 2917

Insertion Sort Python

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

Upvotes: 2

Views: 3520

Answers (3)

Neil
Neil

Reputation: 2438

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.

Upvotes: 2

kasavbere
kasavbere

Reputation: 6003

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.

Upvotes: 1

Radio-
Radio-

Reputation: 3171

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.

Upvotes: 1

Related Questions