mardi 28 novembre 2017

conversion from if statements to efficient for loop based solution for INSERTION SORT in Python

I have the following code that performs an insertion sort for 4 items in a list. It works, but it uses IF statements. I am interested in the various solutions that show a)conversion (based on my code and variables) to a simpler more efficient algorithm using loops where there is repetition and b) a clear explanation as to where/why what has been implemented.

The code for the insertion sort using IF statements:

def main():
  list=[4,1,2,6]
  print("original list:",list)
  cv=list[1]
  if cv<list[0]:
    list[1]=list[0]
    list[0]=cv
    print("Compare element 1 with 0:",list)

  cv=list[2]
  if cv<list[1]:
    list[2]=list[1]
    list[1]=cv
    print("Compare element 2 with 1 & shift 1 upto 2:",list)
    if cv<list[0]:
      list[1]=list[0]
      list[0]=cv
      print("Compare element 2 with 0 and shift 0 and 1 up:",list)

  cv=list[3]
  if cv<list[2]:
    list[3]=list[2]
    list[2]=cv
    print("Compare element 3 with 2 & shift 2 upto 3:",list)
    if cv<list[1]:
      list[2]=list[1]
      list[1]=cv
      print("Compare element 3 with 1 and shift 1 and 2 up:",list) 
      if cv<list[0]:
        list[1]=list[0]
        list[0]=cv
        print("Compare element 3 with 0 and shift 0 up:",list)

main()

How does this code above translate into a for loop/loop based solution + I'd also be interested in a recursive solution, but again derived directly from this one for teaching/learning purposes.

One could start, for example, by reocgnising that each iteration is done for lengthoflist-1 times.

So:

 for i in range((len(list))-1):
    cv=list[i+1]
    etc

I get that there will be an outer loop and an inner loop. How are these best constructed, and again, a clear explanation as to how the solution is derived from this original if-based code, is what I'm after.

Aucun commentaire:

Enregistrer un commentaire