Functions called: (regardless of class)
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
main code
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)
so this code is supposed to take a list and sort it using a median of 3 implementation of quicksort, up until it reaches a depth recursion limit, at which point the the function will instead use heapsort.the results of this code are then fed into another program designed to test the algorithm with lists of length 1,10,100,1000,10000,100000.
however, when I run the code, tells me that lengths 1 and 10 work fine, but after that, it gives an list index out of bounds error for
start=lst[0] in the median of 3 function
I cant figure out why.
Without seeing your test data, we're flying blind here. In general,
is fine on its own, but you never check
less
ormore
to see whether they're empty. Even if they are empty, they're passed on via:and
quicheSortRec()
doesn't check to see whether they're empty either: it unconditionally calls:and that function will raise the error you're seeing if it's passed an empty list. Note that your
quicheSort()
does check for an empty input. The recursive worker function should too.BTW, consider this rewrite of
medianOf3()
:This is one case where brevity is clearer ;-)