"list index out of range" error

[sam]

hey everybody, this is my first time posting here. i'm pretty new to
python and programming in general (as you'll soon work out for
yourselves...)

i'm trying to code a version of a selection sort and the heart of the
code is as follows (no_lines is simply the number of items to be
sorted, read out of an input file):

for j in range(0, no_lines):

k = 0
while k < no_lines:
sorted_check = 0
if list_initial[k] < list_initial[k+1]:
temp_str = list_initial[k]
elif list_initial[k] == list_initial[k+1]:
temp_str = list_initial[k]
elif list_initial[k] > list_initial[k+1]:
temp_str = list_initial[k+1]
sorted_check = 1
k += 1

list_initial.remove(temp_str)
list_final.append(temp_str)
no_lines -= 1

if sorted_check == 0:
break

problem is, i keep getting a "list index out of range" error. i've had
this problem before in different contexts with lists in loops.

i thought i had it cracked when it occurred to me that i needed to
decrement no_lines to take into account that list_initial was shrinking
as i deleted sorted items, but i still got the same error. it's
probably something trivial, but i can't seem to get round it by using
while loops, and i had the same problem with cmp(), hence the explicit
comparison above, which still doesn't work. can anyone help a beginner
out with this?

many thanks in advance,

sam lynas

 

[sam]

actually, that little bit of code i wrote is obscenely wrong anyway, so
please don't bother analyzing the flow.

any insight into the "list index out of range" error would still be
welcome, though.

 

[Marc 'BlackJack' Rintsch]

i'm trying to code a version of a selection sort and the heart of the
code is as follows (no_lines is simply the number of items to be
sorted, read out of an input file):

for j in range(0, no_lines):

k = 0
while k < no_lines:
sorted_check = 0
if list_initial[k] < list_initial[k+1]:
temp_str = list_initial[k]
elif list_initial[k] == list_initial[k+1]:
temp_str = list_initial[k]
elif list_initial[k] > list_initial[k+1]:
temp_str = list_initial[k+1]
sorted_check = 1
k += 1

list_initial.remove(temp_str)
list_final.append(temp_str)
no_lines -= 1

if sorted_check == 0:
break

problem is, i keep getting a "list index out of range" error. i've had
this problem before in different contexts with lists in loops.

i thought i had it cracked when it occurred to me that i needed to
decrement no_lines to take into account that list_initial was shrinking
as i deleted sorted items, but i still got the same error. it's
probably something trivial, but i can't seem to get round it by using
while loops, and i had the same problem with cmp(), hence the explicit
comparison above, which still doesn't work. can anyone help a beginner
out with this?

It has nothing to do with `cmp()` vs. explicit testing but with indexing
the `k+1` element. Let's assume `no_lines` is 10 then the elements have
the indexes 0 to 9. Within the while loop `k` is incremented and the loop
body is executed as long as `k < 10`. When `k == 9` you try to access the
element at index `k+1`, but there is no element at index 10. So you get
the `IndexError`.

Ciao,
Marc 'BlackJack' Rintsch

 

[sam]

yes, yes, of course, thank you. not sure what i thought i was doing
there.
i'll see if i can get it running now...

 

[sam]

for what it's worth. and it is approx. five times quicker than the
bubblesort i wrote to begin with on a 286-word highly unordered list,
so i wasn't wasting my time after all...

______________________________________________________________________
import time

file_input = open('wordlist.txt', 'r')

list_initial = []

no_lines = 0

for line in file_input:
list_initial.append(line)
no_lines += 1

no_lines_2 = no_lines

print list_initial

file_input.close()

raw_input('press enter to sort: ')

list_final = []
temp_str = ""

time1 = time.clock()

for j in range(no_lines_2):

temp_str = 'zzzzzzzzzzzzzzzzzz'
for k in range(no_lines):
if temp_str > list_initial[k]:
temp_str = list_initial[k]
list_initial.remove(temp_str)
list_final.append(temp_str)
no_lines -= 1

time2 = time.clock()
final_time = time2 - time1
print list_final
print
print 'number of seconds for sort list: ', final_time
print
print 'number of words in list: ', no_lines_2
___________________________________________________________________

thanks again for your help. that sorted out something that had really
been bugging me.

 

[Ben Finney]

hey everybody, this is my first time posting here. i'm pretty new to
python and programming in general (as you'll soon work out for
yourselves...)

On behalf of the entire Python community, *thank you* for putting this
disclaimer only in the body of your message and using the Subject
field for a descriptive summary of the topic.

There are far too many threads where the only information available
from the Subject is "I'm a newbie, help!" which is worse than useless
for knowing what the thread is about. Thank you for not following this
tedious trend!

 

[Gabriel Genellina]

thanks again for your help. that sorted out something that had really
been bugging me.

Now that your main problem is gone, just a few comments:
- python lists know their length, so you don't need explicit no_lines
and no_lines_2
- list_initial.remove(temp_str) is fairly slow - it has to *scan* the
list to locate temp_str. Just keep its index instead, and use del
list_initial[index]
- as a general sorting routine, that 'zzz....' does not look very
good, try to avoid it.



Gabriel Genellina
Softlab SRL





__________________________________________________
Preguntá. Respondé. Descubrí.
Todo lo que querías saber, y lo que ni imaginabas,
está en Yahoo! Respuestas (Beta).
¡Probalo ya!
http://www.yahoo.com.ar/respuestas

 

[sam]

gabriel,

Now that your main problem is gone, just a few comments:
- python lists know their length, so you don't need explicit no_lines
and no_lines_2
- list_initial.remove(temp_str) is fairly slow - it has to *scan* the
list to locate temp_str. Just keep its index instead, and use del
list_initial[index]

i will try rewriting it in that manner and comparing the times. i have
no feel so far for the relative speeds of different ways of doing
things, but i can see the importance of it.

- as a general sorting routine, that 'zzz....' does not look very
good, try to avoid it.

yes, it's hideous even to a novice. however, i need to go to bed now,
and if i hadn't got this to work before bed, i'd never get to sleep!
i'll have to mull it over and come up with something more elegant.


ben,

i used to work for a company where we exchanged a lot of e-mails, and
the titles were always 're: your e-mail', or 'project stuff', or 'file
for client' or suchlike. made it kind of difficult to find anything.
figured a similar principle might apply here... ; )

thanks again all,

sam

 

[Tuomas]

sam wrote:

I gues: no_lines=len(list_initial)

for j in range(0, no_lines):

range returns 0, 1, 2, ..., no_lines-1

k = 0
while k < no_lines:
sorted_check = 0
if list_initial[k] < list_initial[k+1]:

When j gets its last value (no_lines-1) k has the same value and k+1
owerflows the list index range.

Try

for j in range(1, no_lines):
...
if list_initial[k-1] < list_initial[k]:
...

Tuomas

temp_str = list_initial[k]
elif list_initial[k] == list_initial[k+1]:
temp_str = list_initial[k]
elif list_initial[k] > list_initial[k+1]:
temp_str = list_initial[k+1]
sorted_check = 1
k += 1

list_initial.remove(temp_str)
list_final.append(temp_str)
no_lines -= 1

if sorted_check == 0:
break

....