Debugging Heapsort in Python

Question

I know how to program in Java, I am very new to python. I am trying to implement HeapSort in Python but I am unable to get where this code went wrong. Can anyone help ?

This is my implementation:

class HeapSort:

    def sort(self,list):
        self.p = list
        self.N = len(list)
        for k in range(N/2,1,-1):
            sink(k,N)

        while N> 1:
            exch(1,N)
            N -=1
            sink(1,N)

# Helper Functions to restore the heap invariant

    def sink(k,N):
        while 2*k <= N:
            j = 2*k
            if (j<N & (j < j+1)):
                j += 1
            if (j < k):
                break
            exch(k,j)
            k = j

    def exch(i,j):
        p[i],p[j] = p[j],p[i]

# Helper Functions to debug

    def isSorted(list):
        for k in range(1,len(list)):
            return False
        return True


    L = [6, 4, 2, 8, 1, 9, 3, 0, 12, 5]
    print(L)
    h = HeapSort()
    h.sort(L)
    print(L)

The output I am getting is

[6, 4, 2, 8, 1, 9, 3, 0, 12, 5]
    NameError: "name 'HeapSort' is not defined"

    module body in heapsort.py at line 26
    class HeapSort:
    function HeapSort in heapsort.py at line 64
    h = HeapSort()

C.B. · Accepted Answer · 2014-03-05 21:28:30Z

1

IF your indentation is accurate, it is causing you to try to call HeapSort in your definition of HeapSort.

Instead you would want

class HeapSort():
    ...

def main():
    L = [6, 4, 2, 8, 1, 9, 3, 0, 12, 5]
    print(L)
    h = HeapSort()
    h.sort(L)
    print(L)

if __name__ == '__main__':
    main()

This allows you to run the file in which you define your class, and if other files import the class, it will not run the code.

EDIT

The above will fix the error that you are getting, but if you see @Matt's comments, but you are running tests within your heapsort.py file, you should move these to an external heapsort-tests.py file and import your class with

from heapsort import HeapSort

EDIT 2

If you are treating this as a class you want to use and pass around as an instantiated object, then you need to pass self to all of your methods and call them with self.method_name(), i.e. self.sink(x,y). If not, you would sort by calling something like HeapSort.sort(L) instead of creating h.

edited Mar 5, 2014 at 21:28

answered Mar 5, 2014 at 21:07

C.B.

8,3965 gold badges23 silver badges34 bronze badges

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

7 Comments

Matt Over a year ago

He has to put the HeapSort class in a separate file called heapsort.py.

C.B. Over a year ago

@Matt he doesn't have to. I have a working example of the same thing in a python 2.7 file. Did this change for 3.x?

sri009 Over a year ago

Apologies for keeping the HW question as part of question... I deleted it

sri009 Over a year ago

I am still getting error UnboundLocalError: "local variable 'N' referenced before assignment" But I initialized N as sort function as self.N = len(list) and since I used self it should be available all the class right ?

C.B. Over a year ago

@sri009 that's because you assign it as a self attribute but don't use it as such. self.N = len(list). You probably just want N = len(list) or always reference it as self.N. You will probably get the same problem with p.

|

Collectives™ on Stack Overflow

Debugging Heapsort in Python

1 Answer 1

7 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

7 Comments

Your Answer

Sign up or log in

Post as a guest

Related