Incrementing and decrementing index in insertion sort-CodePudding

In the code below, I am not sure what the i -= 1 is doing. I know it's decrementing the index by 1 each time it runs through the for loop but exactly how is that helping to sort?

def insertionSort(ls):
    for i in range(1, len(ls)):
        while ls[i-1] > ls[i] and i > 0:
            ls[i], ls[i-1] = ls[i-1], ls[i]
            i -= 1
            print(i)
    return ls

listA = [5,5,3,9,1,4,9,7,3]
result = insertionSort(listA)
print(result)

CodePudding user response：

It doesn't help to sort, it's there for the index to reach zero at some point. If you wouldn't add it, it would result in an infinite loop.

CodePudding user response：

The i-= 1 iterates i from it's current value (set by the outer loop) downwards until the current element you're sorting is in the correct place.

e.g.

def insertionSort(ls):
    for i in range(1, len(ls)):
        print(f"Outer loop. i is set to {i}")
        print(ls)
        while ls[i-1] > ls[i] and i > 0:
            ls[i], ls[i-1] = ls[i-1], ls[i]
            i -= 1
            print(i)
    return ls

listA = [5,5,3,9,1,4,9,7,3]
result = insertionSort(listA)
print(result)

Output (with comments):

Outer loop. i is set to 1
[5, 5, 3, 9, 1, 4, 9, 7, 3] # 5 >= 5, so move onto the next loop without iterating
Outer loop. i is set to 2 
[5, 5, 3, 9, 1, 4, 9, 7, 3] # 3 < 5, so iterate i downwards until i = 0  
1
0
Outer loop. i is set to 3
[3, 5, 5, 9, 1, 4, 9, 7, 3] # 9 >= 5, so move onto the next loop without iterating
Outer loop. i is set to 4
[3, 5, 5, 9, 1, 4, 9, 7, 3] # 1 is the smallest of the sorted list, so iterate i downwards until i = 0
3
2
1
0
Outer loop. i is set to 5
[1, 3, 5, 5, 9, 4, 9, 7, 3] # 4 belongs between 3 and 5, so iterate i downwards until i = 2
4
3
2
Outer loop. i is set to 6 
[1, 3, 4, 5, 5, 9, 9, 7, 3] # 9 >= 9, so move onto the next loop without iterating
Outer loop. i is set to 7
[1, 3, 4, 5, 5, 9, 9, 7, 3] # 7 belongs between 5 and 9, so iterate i downwards until i = 5
6
5
Outer loop. i is set to 8
[1, 3, 4, 5, 5, 7, 9, 9, 3] # 3 belongs between 3 and 4, so iterate i downwards until i = 2
7
6
5
4
3
2
[1, 3, 3, 4, 5, 5, 7, 9, 9]