Why does it mark me list index out of range?

Question

Why does it mark me list index out of range?

Navigation

#1 by (4 votes)
#2 by (2 votes)

2

Can someone tell me what error I have in my code if it is not too much trouble.

def CreaLista(k):
    L = []
    for i in range(k+1):
        L.append(0)
    return L

def CountingSort(A,k):
    C=CreaLista(k)
    B=CreaLista(len(A)-1)
    for j in range(1, len(A)):
        C[A[j]] = C[A[j]]+1
    for i in range(1, k+1):
        C[i]=C[i]+C[i-1]
    for j in range(len(A)-1,0,-1):
        B[C[A[j]]]=A[j]
        C[A[j]]=C[A[j]]-1
    return B

lista = [0,9,7,81,4,5,68,3,541]
k = len(lista[1:])
CountingSort(lista, k)

This is the error that gives me:

IndexError                                Traceback (most recent call last)
<ipython-input-1-d6ba25f80b3f> in <module>()
     19 lista = [0,9,7,81,4,5,68,3,541]
     20 k = len(lista[1:])
---> 21 CountingSort(lista, k)

<ipython-input-1-d6ba25f80b3f> in CountingSort(A, k)
      9     B=CreaLista(len(A)-1)
     10     for j in range(1, len(A)):
---> 11         C[A[j]] = C[A[j]]+1
     12     for i in range(1, k+1):
     13         C[i]=C[i]+C[i-1]

IndexError: list index out of range

python python-3.x algoritmos

asked by Johan Cancino 27.02.2017 в 09:01

source

2 answers

4

In Python, the lists start with 0. In your case, in the first iteration of the first for, A[j] is 9. C has only 9 elements, so you could only access up to C[8] . In any case, I recommend that you use the enumerate function instead of using range. The for loops would be much cleaner:

for key, value in enumerate(A):
    pass

answered by 27.02.2017 в 13:08

Use order_by in Django Laravel, Form is sent double

score 2 · Accepted Answer

I interpret that you have an implementation error of the CountingSort algorithm. The k parameter should not be the number of items in the list to be sorted, but the maximum value of the list. In the example you show, the maximum value of the list to sort is 541 . Therefore, you should change the call to the function so that k takes the desired value:

lista = [0,9,7,81,4,5,68,3,541]
k = max(lista[1:])  # max() en vez de len()
CountingSort(lista, k)