pythonalgorithmsortinginsertion-sort

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 

Solution

  • 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.