CODEWITHSUNDEEP
pythoninsertion-sortinsertion
Ben
Ben

Reputation: 21

Insertion sort error list index

I am trying to create an array of 7 randomly generated numbers and then sorting these numbers from smallest to highest using the insertion sort method. I have looked through several previously answered topics as it is a very common question but each user has very different code to me which makes me wonder where I am going wrong. 

import random # importing the random module
arrayInsertion = []

for i in range (7): # 7 different numbers
    arrayInsertion.append(random.randint (1,10))

for i in range (1,7):
    while  i > 0 and arrayInsertion [i+1] > arrayInsertion [i]:
        arrayInsertion [i] = arrayInsertion [i-1]
        i = i - 1
print (arrayInsertion)

When running this code I get the following error message:

Traceback (most recent call last): File "C:\Users\Ben\Desktop\insertion sort.py", line 8, in while i > 0 and arrayInsertion [i+1] > arrayInsertion [i]: IndexError: list index out of range

Upvotes: 0

Views: 100

Answers (4)

MYC2E
MYC2E

Reputation: 11

def insert_sort(list_input):
    for unsorted_id in range(len(list_input)):
        element = list_input[unsorted_id]
        sorted_id = unsorted_id - 1
        while sorted_id >= 0 and element > list_input[sorted_id]:
            list_input[sorted_id + 1] = list_input[sorted_id]
            sorted_id -= 1
        list_input[sorted_id + 1] = element
    return list_input

Upvotes: 0

Ajay Singh
Ajay Singh

Reputation: 1281

for i in range(1,7)

Above line of code will produce 1 to 6 sequentially (1,2,3,4,5,6)

while  i > 0 and arrayInsertion [i+1] > arrayInsertion [i]

arrayInsertion [i+1] in above line in try to access arrayInsertion[7] for i = 6 which is not present

So It will throw IndexError: list index out of range

Upvotes: 0

Jonathan
Jonathan

Reputation: 303

you could also just use the built in .sort() method

Upvotes: 0

vallentin
vallentin

Reputation: 26215

The problem is arrayInsertion[i + 1] when i = 7 then i is out of bounds, since there's only 7 elements in the list. You're also not remembering the current value and index.

for i in range(1, len(arrayInsertion)):
    curr = arrayInsertion[i]
    pos = i
    while pos > 0 and arrayInsertion[pos - 1] > curr:
        arrayInsertion[pos] = arrayInsertion[pos - 1]
        pos -= 1
    arrayInsertion[pos] = curr

Which correctly yields:

[5, 5, 5, 6, 6, 8, 9]

For future use consider packing it into a function def insertion_sort(a).

Upvotes: 1

Related Questions