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]