Sort an Array in Place, Largest First, With No Second Array
Sort an Array in Place, Largest First, With No Second Array
The lab's min_heap_sort builds a separate heap, which needs a second block of memory as big as the array. Complete sift_down and heap_sort_descending so the array is sorted with no extra memory at all: the array itself is the heap. The result is in DESCENDING order (largest first).
Reminder: a heap is only a way of reading an array. There is no struct in this question. The first count slots of the array are treated as a min heap: the parent of index i is at (i - 1) / 2, its children are at 2 * i + 1 and 2 * i + 2, and a child exists only when its index is less than count. Every parent is smaller than or equal to its children, so the smallest value is at index 0.
The idea has two phases. First turn the whole array into a min heap, bottom-up. Then repeat: the smallest value is at index 0, so swap it with the LAST slot of the heap, and say the heap is now one slot shorter. The slot you just filled is finished and never touched again. The value that landed on the root sinks back into place within the shorter heap.
the heap part is on the left of the bar, the finished part on the right:
as a min heap: 1 3 2 7 |
swap slot 0 and 3: 7 3 2 | 1 the smallest is now last
sink 7 (heap of 3): 2 3 7 | 1
swap slot 0 and 2: 7 3 | 2 1
sink 7 (heap of 2): 3 7 | 2 1
swap slot 0 and 1: 7 | 3 2 1
result: 7 3 2 1 (largest first, because each smallest value was sent to the back)This is why sift_down takes the count as a parameter: the heap keeps shrinking, and a sink must never reach into the finished part.
Requirements:
1. sift_down(values, count, i): while index i has a left child inside the first count slots, pick the smaller child (the right one only when it exists and is smaller); stop when values[i] is less than or equal to it, otherwise swap them with swap_values and continue from the child.
2. heap_sort_descending(values, count): first call sift_down for every index from count / 2 - 1 down to 0. Then for end from count - 1 down to 1: swap values[0] with values[end], and call sift_down on index 0 with a heap of end slots.
3. Use no other array and no malloc.
Do NOT write a main function.
Expected Output:
after: 2 4 3 9 5 | 1= newline. The output ends with a newline — print one after the last line.
Your Output
Run your code to see the output here...