Follow

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use
Contact

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?

MEDevel.com: Open-source for Healthcare and Education

Collecting and validating open-source software for healthcare, education, enterprise, development, medical imaging, medical records, and digital pathology.

Visit Medevel

>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.

Add a comment

Leave a Reply

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use

Discover more from Dev solutions

Subscribe now to keep reading and get access to the full archive.

Continue reading