sorting python heaps and lists

Question

I'm trying to do the following problem

purpose: Implementation of the quicheSort algorithm (not in place), It first uses quickSort, using the median-of-3 pivot, until it reaches a recursion limit bounded by int(math.log(N,2)). Here, N is the length of the initial list to sort. Once it reaches that depth limit, it switches to using heapSort instead of quicksort.

import heapSort            # heapSort
import qsPivotMedian3
from math import*                 # log2 (for quicksort depth limit)
import testSorts            # run (for individual test run)

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 len(lst) == 0:
        return lst()
    elif limit > 0:
        quickSort(lst)
    else:
        heapSort(lst)

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
    """
    if len(lst)== 0:
        return list()
    else:
        limit = float(log(len(lst),[2]))
        return quicheSortRec(lst,limit)

if __name__ == "__main__":
    testSorts.run('quicheSort')

The problem i'm having with this code is my limits. I'm supposed to set the limit as int(log(N,[2])). However, python keeps telling me a float is needed. So when I change int to float it still keeps telling me a float is needed.

The traceback -

le "/Users/sps329/Desktop/quicheSort.py", line 44, in <module>
    testSorts.run('quicheSort')
  File "/Users/sps329/Desktop/testSorts.py", line 105, in run
    performSort(sortType, data, N)
  File "/Users/sps329/Desktop/testSorts.py", line 71, in performSort
    result = sortType.function(dataSet.data)
  File "/Users/sps329/Desktop/quicheSort.py", line 40, in quicheSort
    limit = float(log(len(lst),[2]))
TypeError: a float is required

Replace [2] with 2. It makes no sense to take the log with respect to a list ;-) — Tim Peters
– Tim Peters, Commented Dec 2, 2013 at 21:45
the way you use this limit is weird. It should be computed once on the complete list, then a counter should be incremented at each level of recursion and compared to that value. — njzk2
– njzk2, Commented Dec 2, 2013 at 21:46

user2357112 · Accepted Answer · 2013-12-02 21:45:32Z

2

        limit = float(log(len(lst),[2]))

[2] is a 1-element list. Why are you making a 1-element list? You just want 2 here. I'd think maybe that was supposed to be mathematical notation for a floor, but flooring 2 doesn't make much sense either.

answered Dec 2, 2013 at 21:45

user2357112

286k32 gold badges490 silver badges570 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

sorting python heaps and lists

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related