0

heap sort naive implementation

I have some trouble with the sort function in the code it doesn't give out the sorted array like i wanted. anybody, help. here's the code: def sift_down(unsorted, index, size): l = 2 * index +1 r = 2 * index +2 largest = index # comparing a node an its left child # size have to be minused 1 since we start at index 0 if l <= size-1 and unsorted[l] > unsorted[largest]: largest = l # comparing either the siblings or the node and its right child if r <= size-1 and unsorted[r] > unsorted[largest]: largest = r if largest != index: unsorted[index],unsorted[largest] = unsorted[largest],unsorted[index] sift_down(unsorted, largest, size) def build_heap(unsorted): size = len(unsorted) # we divide size by 2(to get to the leftmost part of the tree or heap) then minus 1 becoz we have to get to the almost last layer of the tree ->to work with the sub-tree for i in range(size//2-1, -1, -1): sift_down(unsorted, i, size) def sort(unsorted): size = len(unsorted) build_heap(unsorted) # size - 1 as we start at index 0 for i in range(size-1): unsorted[0], unsorted[-1] = unsorted[-1], unsorted[0] size -= 1 sift_down(unsorted, 0, size) print(unsorted) test = [7,6,8,9] test2 = [1,3,7,4,5,6,2] sort(test) # output: [7,9,8,6]

2nd Aug 2018, 11:19 AM
monotom
monotom - avatar
2 odpowiedzi
0
I'd recommend you to put your code in Sololearn Codeplayground so we could check it in interpreter. At first glance I can say i do not see any variable passing between your main routine and subroutines. i. e. your 'largest' variable is not visible outside the subroutine scope.
2nd Aug 2018, 12:52 PM
strawdog
strawdog - avatar
0
here's the code in action:https://code.sololearn.com/ce579xBhfIz2/#py and can you make it clear about you did not see 'that largest' variable is not visible outside the subroutine scope. thank you
2nd Aug 2018, 2:55 PM
monotom
monotom - avatar