CODEWITHSUNDEEP
python
Sidwa
Sidwa

Reputation: 41

indexError:list index out of range

The program is for quick sort with duplicate keys.The code runs perfectly once or twice and then gives the IndexError next time eventhough the list is not empty.When I print the indices they lie within range.Is it a problem with my computer specifically?

EDIT-added the traceback

import random


def partition(n,lo,hi):
    i=lo
    lt=lo    #index showing the start of all duplicate partitioning keys
    gt=hi    #index showing the end of all duplicate partitioning keys
    x=n[lt]

    while(i<=gt):
        while(n[i]<=n[lt] and i<=gt):
            if(x!=n[lt]):
                print("alert!!!")
            if(n[i]<n[lt]): #current alement not a duplicate of partitioning alement
                if(lt<=i):
                    n[lt],n[i]=n[i],n[lt]
                    #print(n)
                i+=1
                lt+=1
            else: #current element is a duplicate partitioning alement
                #print(n[i],"=",n[lt])
                i+=1

        while(n[gt]>n[lt] and i<=gt):
            gt-=1

        if(i<gt):
            n[i],n[gt]=n[gt],n[i]
            gt-=1
            #print(n)


    return gt



def quickSort(n,lo,hi):
    #print("called")
    if(lo<hi):
        print(n)
        p=partition(n, lo, hi)
        quickSort(n, lo, p-1)
        quickSort(n, p+1, hi)

def main():
    nums=[]
    for i in range(30):
        nums.append(random.randrange(100))
    print("original array")
    print(nums)
    k=4
    hi=len(nums)-1
    #print(k,"th lowest number is ",quickSelect(nums, 0,hi,k))
    print(nums)
    quickSort(nums,0,hi)
    print(nums)

if __name__ == "__main__":
    main()

Traceback:

Traceback (most recent call last):
  File "C:\Users\S.reddy\workspace\sorter\src\selector\quickSelect.py", line 59, in <module>
    main()   
  File "C:\Users\S.reddy\workspace\sorter\src\selector\quickSelect.py", line 55, in main
    quickSort(nums,0,hi)
  File "C:\Users\S.reddy\workspace\sorter\src\selector\quickSelect.py", line 43, in quickSort
    quickSort(n, p+1, hi)
  File "C:\Users\S.reddy\workspace\sorter\src\selector\quickSelect.py", line 41, in quickSort
    p=partition(n, lo, hi)
  File "C:\Users\S.reddy\workspace\sorter\src\selector\quickSelect.py", line 11, in partition
    while(n[i]<=n[lt] and i<=gt):
IndexError: list index out of range

Upvotes: 0

Views: 773

Answers (2)

Blckknght
Blckknght

Reputation: 104842

Your code was sometimes getting out of bounds indexes because of the order you were checking your conditions in your inner while loop.

Often an easy best way to debug issues like this is to add try and except blocks to the code, with the except block printing out useful diagnostic values. I used this variation on your loop to figure out the issue:

try:
    while(n[i]<=n[lt] and i<=gt):
        if(x!=n[lt]):
            print("alert!!!")
        if(n[i]<n[lt]): #current alement not a duplicate of partitioning alement
            if(lt<=i):
                n[lt],n[i]=n[i],n[lt]
                #print(n)
            i+=1
            lt+=1
        else: #current element is a duplicate partitioning alement
            #print(n[i],"=",n[lt])
            i+=1
except IndexError:
    print(i, gt, len(n))
    raise

You'll see that under certain circumstances, gt will be len(n) - 1 and i will be len(n). In that situation, the first test in while(n[i]<=n[lt] and i<=gt): will raise an IndexError since n[i] is not a valid index.

Instead, you should put the tests in the other order, with the i <= gt first. If that test is False, the and will "short-circuit" and not evaluate the second test, which is the one that would cause the exception. So: use while i <= gt and n[i] <= n[lt]: (The parentheses were unnecessary, so I've removed them and spaced out the terms from the operators. See PEP 8 for more recommendations on Python style.)

Upvotes: 1

ands
ands

Reputation: 2046

The problem is in row 11:

    while(n[i]<=n[lt] and i<=gt):

you need to change it to:

    while(i<=gt and n[i]<=n[lt]):

because python first checks first condition (in this case it is i<=gt) and if it is true than he checks the second one (n[i]<=n[lt]) but if the first condition is false then python exits while loop without checking second condition.

Upvotes: 0

Related Questions