I need to use both heap sorting and quick sort so that it switches to the implementation of heap sorting when the recursion depth exceeds the log base 2 of the size of the original list.
My heap sort function:
import heapq def heapSort(lst): """ heapSort(List(Orderable)) -> List(Ordered) performs a heapsort on 'lst' returning a new sorted list Postcondition: the argument lst is not modified """ heap = [] for item in lst: heapq.heappush(heap, item) sortedlist = [] while len(heap) > 0: sortedlist.append(heapq.heappop(heap)) return sortedlist
My quick sort:
def medianOf3(lst): """ From a lst of unordered data, find and return the the median value from the first, middle and last values. """ a,b,c = lst[0], lst[len(lst)//2], lst[-1] return min(min(max(a,b), max(b,c)), max(a,c)) def quickSort(lst): """ quickSort: List(lst) -> List(result) Where the return 'result' is a totally ordered 'lst'. It uses the median-of-3 to select the pivot eg quickSort([1,8,5,3,4]) == [1,3,4,5,8] """ if lst == []: return [] else: pivot = medianOf3(lst) less, same, more = partition(pivot, lst) return quickSort(less) + same + quickSort(more) def partition( pivot, lst ): """ partition: pivot (element in lst) * List(lst) -> tuple(List(less), List(same, List(more))). Where: List(Less) has values less than the pivot List(same) has pivot value/s, and List(more) has values greater than the pivot eg partition(5, [11,4,7,2,5,9,3]) == [4,2,3], [5], [11,7,9] """ 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
Now I'm trying to implement quipSort so that it switches between heap sorting and quick sort:
def quipSortRec(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: heapSort(lst) else: quickSort(lst) quipSortRec(lst, limit -1) return lst def quipSort(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 """ l = math.log2(len(lst)) return quipSortRec(lst, l)
This is not sorting at all, and I'm a bit lost as something is wrong with my quipSort. My heap sorting and quick sorting work fine.