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.
First of all, never name a list "list" as it overrides the built-in list() function. Instead, I have named it l:
l = [4, 1, 2, 6]
Then, we need to simply do a for-loop that loops over the indexes in l. We need to start at index 1 though (second element) as insertion works by shifting elements left (as you know) and so we should start at the second element and go to the last (so the length of l: len(l)).
Then we want to begin a while loop. This will continue whilst the current element at i (the index) in the list is smaller than the element to its left and i is greater than 0 (so we haven't gone off the end).
For example, in the first iteration of the for-loop, i will be 1 which has the element value of 1 in l. As 1 is greater than l[i-1] (this is 4) and i which is 1 is > 0 which it is, we enter the while.
In the while loop, all we do is switch the current element and the one to its left with the nice syntax stolen from here.
Finally, the last thing to do in the while is to decrease the index by 1 i.e. move the current position to the left so we can then to another switch if it is yet again smaller than the element to its left.
So after all that explanation, here is the code:
for i in range(1, len(l)):
while l[i] < l[i-1] and i > 0:
l[i-1], l[i] = l[i], l[i-1]
i -= 1
which modifies l to:
[1, 2, 4, 6]