CODEWITHSUNDEEP
pythonalgorithmsorting
Robin Andrews
Robin Andrews

Reputation: 3794

Insertion Sort Algorithm Off by One Error

My Python code for the Insertion Sort Algorithm nearly works, but for some reason the first item of my list is not sorted - could someone please tell me where the problem is?

listToBeSorted = [7,2,4,3,6,5,1]
for pointer in range(1, len(listToBeSorted )):
    itemToBeInserted = listToBeSorted[pointer]
    currentIndex = pointer - 1
    while listToBeSorted[currentIndex] > itemToBeInserted and currentIndex > 0:
       listToBeSorted[currentIndex + 1] = listToBeSorted[currentIndex]
       currentIndex -= 1
    listToBeSorted[currentIndex + 1] = itemToBeInserted

print(listToBeSorted)

Upvotes: 0

Views: 52

Answers (2)

Andreas
Andreas

Reputation: 2521

The problem is at this statement

while listToBeSorted[currentIndex] > itemToBeInserted and currentIndex > 0

which should be

while listToBeSorted[currentIndex] > itemToBeInserted and currentIndex > -1

If currentIndex always larger than 0, then the first element of the list never get sorted because no item in the list would be inserted at the beginning of the list.

listToBeSorted = [7,2,4,3,6,5,1]
for pointer in range(1, len(listToBeSorted )):
    itemToBeInserted = listToBeSorted[pointer]
    currentIndex = pointer - 1
    while listToBeSorted[currentIndex] > itemToBeInserted and currentIndex > -1:
       listToBeSorted[currentIndex + 1] = listToBeSorted[currentIndex]
       currentIndex -= 1
    listToBeSorted[currentIndex + 1] = itemToBeInserted

print(listToBeSorted)

Upvotes: 1

Blckknght
Blckknght

Reputation: 104712

Your code ends the while loop too early. Instead of currentIndex > 0, you want currentIndex >= 0, so that you can shift the first value in the list forwards if necessary.

Upvotes: 1

Related Questions