CODEWITHSUNDEEP
pythonsorting
Michael Taylor
Michael Taylor

Reputation: 19

Python "IndexError: string index out of range" (Beginner)

So for a Programming assignment we have to re write the sort function in python to sort a list of words. So far I have made it able to sort the words based of the first letter of each and now im trying to run recursion to still sort it if the first letters or any of the letters are the same. Im having problems with the "IndexError: string index out of range" error. What I have so far is 

def insertion_sort(bookwords):
    for index in range(1,len(bookwords)):
        global word
        word=bookwords[index]
        i=index-1
        word_checker(bookwords, 0, i)

def word_checker(bookwords, num, i):
    while i>=0:
        wordleft=bookwords[i]
        if ord(word[num])<ord(wordleft[num]):
            bookwords[i+1]=bookwords[i]
            bookwords[i]=word
            i=i-1
        elif ord(word[num])==ord(wordleft[num]):
            num=num+1
            word_checker(bookwords, num, i)
        else:
            break


bookwords=["michael", "maddy", "michelle", "monstor", "money", "mountain", "miniscus", "mega"]

insertion_sort(bookwords)

print bookwords

Im guessing num is becoming larger than the words but its running through many times without stopping when the letters arn't the same so im abit confused why its doing that. Any help would be greatly appreciated

UPDATE

Ok now it works but when I put it into the supplied code to test how fast it is with about 700000 words it went for 30+ until I stopped it where as the sort function took 5 seconds. Here is the code with my part as well

import re
import pygame

# 159.172 assignment 2
# 
def mysort(words):
for index in range(1,len(words)):
    word=words[index]
    i=index-1
    word_checker(words, i, word)

def word_checker(words, i, word):
while i>=0:
    wordleft=words[i]
    if word==wordleft:
        break
    elif word<wordleft:
        words[i+1]=words[i]
        words[i]=word
        i=i-1
    else:
        return

# Do NOT change anything below here:
#
# Compare two lists
def compare(l1,l2):
    if len(l1) != len(l2):
        return False
    for a,b in zip(l1,l2):
        if a!=b:
            return False
    return True

# Open the book
book=open("allsherlock.txt", "rt")

# Make a list of all the words in the book
bookwords=[]
for line in book:
    for word in re.findall(r'\w+', line):
        bookwords.append(word.lower())

print "Loaded",len(bookwords),"words"
sortedbookwords=bookwords[:]
pygame.init()
# Use the sort function to sort the words for testing
sortedbookwords.sort()
starttime=pygame.time.get_ticks()
# Call our sort function
mysort(bookwords)
print "Sort took",pygame.time.get_ticks()-starttime,"ms"
print "Correct sort:",compare(bookwords,sortedbookwords)

Upvotes: 1

Views: 1644

Answers (2)

Foo Bar User
Foo Bar User

Reputation: 2491

you have to change this:

 elif ord(word[num])==ord(wordleft[num]):
     num=num+1
     word_checker(bookwords, num, i)
 else:

to:

 elif ord(word[num])==ord(wordleft[num]):
     num=num+1
 else:

then it will print: ['maddy', 'mega', 'money', 'michael', 'michelle', 'miniscus', 'monstor', 'mountain']

i don't see the point of doing recursion there anyway, i think insertion sort doesn't do recursion.

update

The algorithm was broken when comparing by character, but python can compare the strings for you, so this will give the right result:

def insertion_sort(bookwords):
    for index in range(1,len(bookwords)):
        global word
        word=bookwords[index]
        i=index-1
        word_checker(bookwords, i)

def word_checker(bookwords,  i):
    while i>=0:
        wordleft=bookwords[i]
        if word<wordleft:
            bookwords[i+1]=bookwords[i]
            bookwords[i]=word
        i=i-1

bookwords=["michael", "maddy", "michelle", "monstor", "money", "mountain", "miniscus", "mega"]
insertion_sort(bookwords)
print bookwords #prints ['maddy', 'mega', 'michael', 'michelle', 'miniscus', 'money', 'monstor', 'mountain']

Upvotes: 3

Kirbinator
Kirbinator

Reputation: 213

Several things:

  • Python zero-indexes strings (so from 0 to len(string)-1). and
  • Consider just using "for" to go through each letter.

Upvotes: 1

Related Questions