indexError: индекс индекса за пределами допустимого диапазона

Question

Программа предназначена для быстрого сортировки с повторяющимися ключами. Код работает отлично один или два раза, а затем дает IndexError в следующий раз, хотя список не пуст. Когда я печатаю индексы, которые они лежат в пределах диапазона .Это проблема с моим компьютером?

EDIT-добавил отслеживающий

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 

Answer 1

Ваш код иногда выходил за пределы индексов из-за того, что вы проверяли свои условия в своем внутреннем цикле while.

Часто простой лучший способ отладки проблем, как это добавить try и except блок кода, с except блоком распечатки полезных диагностических значений. Я использовал этот вариант на вашем цикле, чтобы выяснить вопрос:

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 

Вы увидите, что при определенных обстоятельствах gt будет len(n) - 1 и i будет len(n). В этой ситуации первый тест в while(n[i]<=n[lt] and i<=gt): поднимет IndexError, так как n[i] недействительный индекс.

Вместо этого вы должны поставить тесты в другом порядке, сначала с i <= gt. Если этот тест равен False, то and будет «короткозамкнуто» и не будет оценивать второе испытание, которое будет причиной исключения. Итак: используйте while i <= gt and n[i] <= n[lt]: (Скобки не нужны, поэтому я удалил их и отделил термины от операторов. См. PEP 8 для получения дополнительных рекомендаций по стилю Python.)

Answer 2

Проблема заключается в строке 11:

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

вам нужно изменить его на:

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

, потому что python сначала проверяет первое условие (в этом случае это i < = gt), и если оно верно, то он проверяет второй (n [i] < = n [lt]), но если первое условие является ложным то python завершает цикл while без проверки второго условия.