1

I have an implementation of the Insertionsort algorithm where in the lecture there is a new instance variable before the while loop.

def swap(l, i, j):
    temp = l[i]
    l[i] = l[j]
    l[j] = temp


def ins_sort(l):
    for i in range(len(l)):
        j = i
        while j > 0 and l[j - 1] > l[j]:
            swap(l, j - 1, j)
            j = j - 1


    return l

In my testing and playing around the algorithm worked without it as well though and I do not understand why I would need to write an extra line of code if it is not necessary.

def swap(l, i, j):
    temp = l[i]
    l[i] = l[j]
    l[j] = temp


def ins_sort(l):
    for i in range(len(l)):
        while i > 0 and l[i - 1] > l[i]:
            swap(l, i - 1, i)
            i = i - 1


    return l
Vishal Singh
  • 6,014
  • 2
  • 17
  • 33
LyrikIngwer
  • 11
  • 2

2 Answers2

2

It looks like the original code is a translation from the c/c++ implementation where modifying i inside the loop would be persistent and affect the loop itself. However since in python, i will be reset each iteration, the second code will also work. In short I don't think that line is necessary for a python implementation.

ref:Scope of python variable in for loop

Ameya Rane
  • 286
  • 1
  • 7
-1

You could also try the following program for Insertion sort where the use of the extra variable is not necessary:

l=[4,3,1,2]
for i in range(1,len(l)): 
      key=l[i]  
      for j in range(i-1,-1,-1):
          if l[j]>key:
              l[j+1]=l[j]
          else:
              j=j+1
              break

      l[j]=key

print(l)
qubitybit
  • 53
  • 7