Heap sort Algorithms issue

Question

I followed the clrs book for algo. I'm trying make heapsort in python. But It give me the error that r falls out side of the index but I don't know why.

def Max_Heapify(A,i,size_of_array):
    l = 2*i
    r = l + 1
    if l <= size_of_array and A[l] > A[i]:
        largest = l
    else:
        largest = i
    if r <= size_of_array and A[r] > A[largest]:
        largest = r
    if i != largest:
        A[i], A[largest] = A[largest], A[i]
        Max_Heapify(A,largest,size_of_array)

def Build_Max_Heap(A,size_of_array):
    for i in range((math.floor(size_of_array/2)) - 1 , 0 ,-1):
        Max_Heapify(A,i,size_of_array)

def Heapsort(A,size_of_array):
    Build_Max_Heap(A,size_of_array)
    for i in range(size_of_array - 1 ,0 ,-1):
        A[0],A[i] = A[i],A[0]
        size_of_array = size_of_array - 1
        Max_Heapify(A,0,size_of_array)

All of your indentation in the functions is off. Please fix it and paste the full traceback. — roganjosh
– roganjosh, Commented Oct 22, 2017 at 21:58

Ana Ribeiro · Accepted Answer · 2017-10-22 22:05:44Z

1

In most of the programming languages, the size of the array is bigger than the last index. For example, the following array: A = [1, 2, 3], its size is 3, but the index of the last element is 2 (A[3] should return that it is out of index). You are verifying if r is less or equal to the array size, so when it is equal, it is bigger than the last index. Your verification should be:

if r < size_of_array

answered Oct 22, 2017 at 22:05

Ana Ribeiro

611 silver badge5 bronze badges

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

1 Comment

Camilo Salazar Over a year ago

if r < size_of_array and A[r] > A[largest]: IndexError: list index out of range So I did that. When I take the array that i'm using it should something like array_1 = array_1 - 1.

Collectives™ on Stack Overflow

Heap sort Algorithms issue

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related