pythonalgorithminsertion-sort

Insertion sort python algorithm: Why do we subtract 1 from i?

Here is the code:

list_a = [3,2,5,7,4,1]

def insertion_sort(list_a):
  indexing_length = range(1,len(list_a))

  for i in indexing_length:
    value_to_sort = list_a[i]

    while list_a[i-1] > value_to_sort and i>0:
      list_a[i], list_a[i-1] = list_a[i-1], list_a[i]  
      i = i - 1
  
  return list_a

I understand the logic to the rest of the algorithm but I can't seem to grasp the logic for doing i = i - 1. Can someone explain please?

Solution

  • in insertion sort, you select each value and go back ward to place in the corresponding place where it is smaller than right part and bigger than left part.

    probably this gif from wikimedia describes it well. if embedded gif not wokring look at the link : https://upload.wikimedia.org/wikipedia/commons/9/9c/Insertion-sort-example.gif

    enter image description here

    for this reason you need the i = i -1 to go backwrd and place in the correct place.