Pass by value or reference with recursion implementing Heap Sort

Question

I am attempting to implement heap sort using the psuedo code from the book Intro to Algorithms. The following is what I have:

def parent(i):
    return i/2

def left(i):
    return 2*i

def right(i):
    return 2*i+1

def max_heapify(seq, i, n):
    l = left(i)
    r = right(i)

    if l <= n and seq[n] > seq[i]:
        largest = l
    else:
        largest = i
    if r <= n and seq[r] > seq[largest]:
        largest = r

    if largest != i:
        seq[i], seq[largest] = seq[largest], seq[i]
        max_heapify(seq, largest, n)

def heap_length(seq):
    return len(seq) - 1

def build_heap(seq):
    n = heap_length(seq)
    for i in range(n/2,0,-1):
        max_heapify(seq, i, n)

def sort(seq):
    build_heap(seq)
    heap_size = heap_length(seq)
    for i in range(heap_size,1,-1):
        seq[1], seq[i] = seq[i], seq[1]
        heap_size = heap_size - 1
        max_heapify(seq, 1, heap_size)

    return seq

I am having issues with understanding passing by value or by reference in Python. I have looked at the following question and it seems that I am passing the list by value. My questions is how to return the correctly sorted list either by reference or by value?

Joran Beasley · Accepted Answer · 2012-08-28 23:47:33Z

2

arrays are always passed by reference if you want to pass by value use slice

my_func(my_array[:]) #send copy

my_func(my_array) #array is modified inside and changes are reflected in original

answered Aug 28, 2012 at 23:47

Joran Beasley

114k13 gold badges167 silver badges187 bronze badges

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

3 Comments

user670595 Over a year ago

Hmm then I wonder if my code is incorrect? When I return the list it doesn't seem to modify the list.

Joran Beasley Over a year ago

x = some_func(ar); would apply any modifications to ar and return a different (or same) array as x

user670595 Over a year ago

Unfortunately I am doing that in my __main__ but I get the unsorted list that I had before.

Collectives™ on Stack Overflow

Pass by value or reference with recursion implementing Heap Sort

1 Answer 1

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related