Why does my insertion sort Algorithm return out of order

Question

I am working on creating a basic insertion sort algorithm using Python.

My textbook shows the psudeocode of an insertion sort algorithm here.

If I follow that convention using python 3, I produce the following code:

def insertionSort(arr):
#Traverse through 1 to len array
   for j in range(1, len(arr)):
       key = arr[j]
       i = j-1
       while i >0 and arr[i] > key:  #this line seems incorrect?
           arr[i+1] = arr[i]
           i = i-1
       arr[i+1] = key
   return arr

If I set arr = [12,11,13,5,6] The result returns as [12,5,6,11,12,13] which obviously is not a correct sort.

After tweaking with the algorithm for some time changing the line I marked as incorrect to while i>=0 and arr[i] > key: the algorithm gives the correct output. Is my book incorrect in omitting the equal sign or am I not understanding how the psuedocode operates within my textbook?

It looks like your correction is right; and if your book omitted the =, it is wrong. — khelwood
– khelwood, Commented Aug 30, 2020 at 21:08
@khelwood, look at the screenshot. The book is using a 1-based indexing. Both are right. — under_the_sea_salad
– under_the_sea_salad, Commented Aug 30, 2020 at 21:11

under_the_sea_salad · Accepted Answer · 2020-08-30 21:09:36Z

2

It looks like you mostly correctly translated the book's algorithm into Python. As you see, the book's algorithm is 1-based while Python is 0-based.

The book's algorithm starts at index 2 but you have to start at index 1.

This also translates to keeping the while loop going until the first index. In the book's case, that's 1 and in your case it should be 0 in Python. So the book is correct but you are also correct (because of the differences in indexing conventions).

answered Aug 30, 2020 at 21:09

under_the_sea_salad

1,8443 gold badges23 silver badges44 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

fusion · Accepted Answer · 2020-08-30 21:07:39Z

1

def insertionSort(arr):
#Traverse through 1 to len array
   for j in range(1, len(arr)):
       key = arr[j]
       i = j-1
       # you need to change here to i>=0
       while i >= 0 and arr[i] > key:  #this line seems incorrect?
           arr[i+1] = arr[i]
           i = i-1
       arr[i+1] = key
   return arr

answered Aug 30, 2020 at 21:07

fusion

1,4179 silver badges13 bronze badges

Collectives™ on Stack Overflow

Why does my insertion sort Algorithm return out of order

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related