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