Как исправить ошибку «IndexError: список индексов вне диапазона»

Question

Я новичок и взял Python и вводные алгоритмы и пытался реализовать то, что я узнал.Я пробовал следующий код, но он неоднократно давал мне «IndexError: список индекса вне диапазона».Сбой в функции разделения, особенно в массиве [0], массиве [pivot] = массиве [pivot], массиве [0] коде.Я не смог это исправить.Любая помощь приветствуется.

from math import floor

def mergeSort(a):           # mergesort function
    if len(a)<2:            # if length of a < 2, return a
        return a
    mid=int(len(a)/2)       # mid point
    x=mergeSort(a[:mid])    # recursivly call mergesort for 0 to mid
    y=mergeSort(a[mid:])    # recursivly call mergesort from mid to end
    result=[]               # empty list
    i=j=0                   # initialize i and j
    while j<len(x) and i<len(y):          
        if x[j]<y[i]:          # if x[j] < y[i], then append result for x[j]
            result.append(x[j])
            j+=1               # increment j by 1
        else:
            result.append(y[i])   # append result for y[i]
            i+=1               # increament i by 1
    result+=x[j:]              # add x[j:] --> result
    result+=y[i:]              # add y[i:] --> result
    return result              # return the result

def findMedian(a):               # find the median
    return mergeSort(a)[floor(len(a)/2)]   # call mergesort

def choosePivot(a):               # choose pivot
  medians=[]                      # empty list
  j=0                             # initialize j
  if len(a)==1:                   # if the len = 1, print the element
      print (a[0])
      return a[0]
  if 5<len(a):                    
      medians.append(findMedian(a[0:5]))      # call findMedian for 0 to 5
  else:
      medians.append(findMedian(a))           # call findMedian for a
  for i in range(1,floor(len(a)/5)):         # divide the input array into 5 groups 
      if i*5<len(a):
          medians.append(findMedian(a[j*5:i*5]))   # call findMedian
      else:
          medians.append(findMedian(a[j*5:len(a)]))
  return choosePivot(medians)        # return choosePivot medians

def partition(array,pivot):        # partition
    array[0],array[pivot]=array[pivot],array[0]   #swap
    j=1                  # intiatalize 

    for i in range(1,len(array)): 
        if array[i]<array[0]:
            array[i],array[j-1]=array[j-1],array[i]   #Swap the number less than the pivot
            j+=1

    array[1],array[j]=array[j],array[1]   #swap the pivot to its rightful place
    return j-1,array     #return index of pivot and the partitioned array

def Selection(array,k):         # selection function
    p=choosePivot(array)      

    if k>len(array):        # if k > length of array, then return -1
        print ("Out of array index")
        return -1

    if len(array)>1:             # if len(array) >1, then
        x,b=partition(array,p)           # call partition func
        if x>k:
            c = Selection(b[:x],k)       # search the left half for the statistic
            return c                     # return c
        elif x<k:
            d= Selection(b[x+1:],k-x-1)   # search the right half for the statistic
            return d                      # return d
        else:
            return array[k]               # return the element if statistic is found

    else:
        return array[0]   #Only one element. Only solution, return as it is.
print (Selection([5,1,48,6,2,4,8,7,5,63,2,1,4,8,99],13))

Answer 1

Как исправить ошибки «индекс вне диапазона»?Отладка.Замечательно читайте: Как отлаживать небольшие программы (# 1) .Используйте операторы print или лучше отладчик, чтобы остановиться на определенных позициях в вашем коде и проверить, что происходит не так.Я использую Visual Studio для этого.

Красная точка - это точка останова - всякий раз, когда код попадает в красную точку, он останавливает выполнение, и я могу осмотреть вещи, которые мне нравятся.Затем я могу продвинуться по линии.Желтая стрелка показывает, в какой строке я.

VS может прикреплять переменные в качестве наложения на ваш исходный код - см. Небольшие фрагменты справа от изображения.

Список инструментов отладки: https://wiki.python.org/moin/PythonDebuggingTools

---

Когда ваша программа проходит через VS в третий раз, она достигает def partition(array,pivot):, она выходит за пределы:

Причина в том, что ваш pivot содержит value , а не индекс, необходимый для его замены.

Даже если вы исправите его на:

def partition(array,pivot):        # partition
    idx = array.index(pivot) # get the index of the value here
    array[0],array[idx]=array[idx],array[0]   #swap
    j=1                  # intiatalize 

    for i in range(1,len(array)): 
        if array[i]<array[0]:
            array[i],array[j-1]=array[j-1],array[i]   #Swap the number less than the pivot
            j+=1

    array[1],array[j]=array[j],array[1]   #swap the pivot to its rightful place
    return j-1,array     #return index of pivot and the partitioned array

При обмене array[1],array[j]=array[j],array[1] вы сталкиваетесь с другой ошибкой из-за слишком большого j:

Вам необходимо исправить свои алгоритмы.

HTH