Вызываемые функции: (независимо от класса)
def partition( pivot, lst ):
less, same, more = list(), list(), list()
for val in lst:
if val < pivot:
less.append(val)
elif val > pivot:
more.append(val)
else:
same.append(val)
return less, same, more
def medianOf3(lst):
"""
From a lst of unordered data, find and return the the median value from
the first, middle and last values.
"""
finder=[]
start=lst[0]
mid=lst[len(lst)//2]
end=lst[len(lst)-1]
finder.append(start)
finder.append(mid)
finder.append(end)
finder.sort()
pivot_val=finder[1]
return pivot_val
основной код
def quicheSortRec(lst,limit):
"""
A non in-place, depth limited quickSort, using median-of-3 pivot.
Once the limit drops to 0, it uses heapSort instead.
"""
if limit==0:
return heapSort.heapSort(lst)
else:
pivot=qsPivotMedian3.medianOf3(lst) # here we select the first element as the pivot
less, same, more = qsPivotMedian3.partition(pivot, lst)
return quicheSortRec(less,limit-1) + same + quicheSortRec(more,limit-1)
def quicheSort(lst):
"""
The main routine called to do the sort. It should call the
recursive routine with the correct values in order to perform
the sort
"""
N=len(lst)
end= int(math.log(N,2))
if len(lst)==0:
return list()
else:
return quicheSortRec(lst,end)
поэтому этот код должен брать список и сортировать его, используя медиану 3 реализации быстрой сортировки, до тех пор, пока он не достигнет предела рекурсии глубины, после чего функция вместо этого будет использовать heapsort. Результаты этого кода затем передаются в другая программа, предназначенная для тестирования алгоритма со списками длиной 1,10,100,1000,10000,100000.
однако, когда я запускаю код, он говорит мне, что длины 1 и 10 работают нормально, но после этого он выдает ошибку индекса списка за пределами границ для
start=lst[0] в медиане 3 функции
Я не могу понять, почему.
