Recursive call in python causes IndexError: list index out of range

Question

I am practicing writing various sort functions in different languages. I wrote a bubble sort in python using a recursive call but I don't know how to properly terminate the recursion. As I have it now the program sorts correctly but extends beyond the parameters of my list and triggers an error: IndexError: list index out of range (on line 29) [i.e. bubblesort(randomList)]

import random
#create a list of 10 random ints between 0-99 to be sorted
def makeRandomList():
    unsortedList=[]
    for i in range(10):
        unsortedList.append(random.randrange(100))
    print unsortedList
    return unsortedList


def bubblesort(randomList):
    i=0
    while i<=len(randomList):
        if randomList[i] > randomList[i+1]:
            randomList[i], randomList[i+1] = randomList[i+1], randomList[i]
            i+=1
            if i<len(randomList):
                bubblesort(randomList)
            else: break
        else:
            i+=1
            #for testing purposes
            print randomList
    return randomList


randomList=makeRandomList()
sortedList=bubblesort(randomList)
print "sorted list: ", sortedList

the problem here looks like is yours index use, with this you have to make sure that i and i+1 both are less than len(someList) because in last case, say your list len is 3, when i is 2, i+1 is 3 and is a index out of range... — Copperfield
– Copperfield, Commented Dec 22, 2015 at 4:45

mzee · Accepted Answer · 2015-12-22 05:02:47Z

1

I solved my problem. My index was running off the end of the list (that is, when i was len(randomList) my program was looking for len(randomList+1) and it wasn't terminating at the base case because then while loop was i<=len(randomList) when it should have been i<(len(randomList)-1). Here is the correct solution:

def bubblesort(randomList):
    i=0
    while i<(len(randomList)-1):
        if randomList[i] > randomList[i+1]:
            randomList[i], randomList[i+1] = randomList[i+1], randomList[i]
            i+=1
            if i<(len(randomList)-1):
                bubblesort(randomList)
            else: break
        else:
            i+=1
            print randomList
    return randomList

answered Dec 22, 2015 at 5:02

mzee

551 silver badge11 bronze badges

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

1 Comment

ilyas patanam Over a year ago

Also the way your recursion was defined inorder was incorrect.

ilyas patanam · Accepted Answer · 2015-12-22 05:15:51Z

1

This error was edited from the originally posted code.

Is this line doing what you expect?

randomList[-i]<[-(i+1)]

Here you are just comparing the element randomlist[-i] with the [-(i+1)]. [-(i+1)] is just an integer and not an element of randomlist. It should read

randomList[-i]<randomlist[-(i+1)]

if you are trying to compare the elements of the list.

More efficient way to create a random list of size 10:

When creating an unsorted list of integers, take advantage of random.sample()so you do not waste time and space iterating. In your case, random.sample(range(100), 10).

edited Dec 22, 2015 at 5:15

answered Dec 22, 2015 at 4:42

ilyas patanam

5,3722 gold badges31 silver badges33 bronze badges

Comments

dolan · Accepted Answer · 2015-12-22 04:42:18Z

0

Your inOrder function doesn't work. i is a variable scoped to the function so setting i+=1 at the beginning means that it won't be set to that in the next recursive call.

answered Dec 22, 2015 at 4:42

dolan

1,81414 silver badges22 bronze badges

Comments

Kyle Burns · Accepted Answer · 2015-12-22 04:44:41Z

you can use this to increase the amount of recursive calls you have:

sys.setrecursionlimit(10000)

i would also suggest trying to avoid making recursive methods, for the reason you have.

you should run through the list to get a minimum value and max and then try and predict position of the values. So if the selected item in the list is less than 100 put it into position 10. Or you could could check if the value before it is greater or less than it and if its less than it then do it to the value after it :) for example:

    Age = [10,11,20,9,10,2,1,3]

for X in range(0, len(Age)):
    if X < len(Age) - 1:
        if Age[X] > Age[X + 1]:
            Temp = Age[X + 1]
            Age[X + 1] = Age[X]
            Age[X] = Temp

print(Age)

the output was: [10, 11, 9, 10, 2, 1, 3, 20]

you would want to have a while loop surounding the for loop :)

Collectives™ on Stack Overflow

Recursive call in python causes IndexError: list index out of range

4 Answers 4

1 Comment

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related