pythonsortinginsertion-sort

insertionsort different algorithm


I wanted to write insertionsort algorithm in a different way but I can not understand why my code does not work properly.

def insertionsort(x):
  i=1
  index=0
  while(i>=1 and i<len(x)): #starts from the first index
    j=i-1 #comparing starts from one index lower
    while(0<=j<i): #determines the range of j
      if(x[j]>x[i]):
        x[j+1]=x[j]
        j=j-1  #decrements j up to -1
      else:
        index=j+1 #determines the place where i th element of the list go.
        break
      
    index=j+1
    x[index]=x[i]
    i=i+1 #increments i continues with unsorted list
  return x #returns the value and print(insertionsort[1,5,8,2,7,4]) gives [1,5,8,8,8,8]

Solution

  • The problem is that when you copy values forward, you overwrite the main value at index i that is supposed to be moved later to index index.

    You need to safeguard that value in a temporary variable so you ensure that you always work with the same value, and not with what might have been moved forward.

    Here is your code with only that correction made. Comments indicate where changes were made:

    def insertionsort(x):
      i=1
      index=0
      while(i>=1 and i<len(x)):
        j=i-1
        val = x[i]  # save the value that needs to move
        while(0<=j<i):
          if(x[j]>val):  # compare with saved value
            x[j+1]=x[j]
            j=j-1
          else:
            index=j+1
            break
          
        index=j+1
        x[index]=val  # move saved value
        i=i+1
      return x
    

    Side node: this is not how to write code in a pythonic way. Use for...in loops.