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

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?

CodePudding user response：

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 :

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

CodePudding user response：

Hi and welcome to SO,

range(a, b) in python is equivalent to [a, b[ in mathematics with a and b two floating numbers and a < b

And range(b) is equivalent to [0, b[ in mathematics.

CodePudding user response：

Without,i=i-1 the adjacent elements are checked once. so, at the end [2,3,5,7,4,1] would become [2,3,5,4,1,7] . For this (without i = i-1) to work you need to implement double for loop like below and may replace while loop with if condition or leave as it is.

def insertion_sort(list_a):
  indexing_length = range(1,len(list_a))
  #this is double for-loop
  for _ in indexing_length:
      for i in indexing_length:
        # print(i)
        value_to_sort = list_a[i]
        if list_a[i-1] > value_to_sort and i>0:
          list_a[i], list_a[i-1] = list_a[i-1], list_a[i]  
        print(list_a)
  
  return list_a

Actually above method is easy to understand and taught everywhere where we check every two adjacent elements twice, But to reduce the number of comparisons checks we can use while loop with i = i-1.

CodePudding user response：

Consider an example: arr = [12, 11, 13, 5, 6]

The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.

First Pass:

Starting with first two elements

   12          11          13          5       6

Here, 12 is greater than 11 hence they are not in the ascending order and 12 is not at its correct position. Thus, swap 11 and 12. So, for now 11 is stored in a sorted sub-array.

Second Pass:

Now, move to the next two elements and compare them

   11          12          13          5       6

Here, 13 is greater than 12, thus both elements seems to be in ascending order, hence, no swapping will occur. 12 also stored in a sorted sub-array along with 11.

Third Pass:

Now, Moving forward to the next two elements which are 13 and 5

   11          12          13          5       6

Both 5 and 13 are not present at their correct place so swap them

   11          12          5       13          6

After swapping, elements 12 and 5 are not sorted, thus swap again

   11          5       12          13          6

Here, again 11 and 5 are not sorted, hence swap again

   5       11          12          13          6

here, it is at its correct position

Then we repeat same process in each pass.

You can see from example when one pair of elements isn't in the correct order we keep swapping them from the index of current element backwards till they are in the correct order. that's why we set i = i - 1 in the algorithm code.