CJCoding With Joseph
15free / daySign inCreate account

Sort an Array Where Every Value Is at Most k Slots Away

Write sort_nearly_sorted. The array it gets is almost in order: every value sits at most k slots away from where it belongs in the sorted array. Sort it into ascending order using a heap that never holds more than k + 1 values.

Reminder: how this min heap is stored. A min_heap is a struct with three fields: capacity (the most values it can hold), count (how many it holds now) and values (a pointer to an array made with malloc). The heap is a complete binary tree kept in that array, filled row by row with no gaps, so only slots 0 to count - 1 are in use. Every parent is smaller than or equal to its children, so the smallest value is always at index 0. For the value at index i, the parent is at (i - 1) / 2 and the children are at 2 * i + 1 and 2 * i + 2.

The lab's min_heap_sort puts ALL the values in a heap. Here that is wasted work. If nothing is more than k slots out of place, the value that belongs in slot 0 must be one of the first k + 1 values. So a small heap is enough: it acts as a window that slides along the array. Whenever the window is full, its smallest value is the next one in sorted order.

k = 2, so the heap has room for 3:        values: 3 1 2 6 4 5

  read 3, 1, 2      heap holds 1 2 3       (full)
  read 6            remove 1 -> slot 0,    then insert 6    heap holds 2 3 6
  read 4            remove 2 -> slot 1,    then insert 4    heap holds 3 4 6
  read 5            remove 3 -> slot 2,    then insert 5    heap holds 4 5 6
  nothing left      remove 4, 5, 6 -> slots 3, 4, 5

  result: 1 2 3 4 5 6

It is safe to write the sorted values back into the same array: by the time a value is written into a slot, that slot has already been read into the heap.

The heap functions are already written and tested, the same ones as in your lab. As with the lab's header file, this file shows only their prototypes. The tests print the sorted array AND the room of the largest heap your function asked min_heap_initialize for, so a heap with room for everything does not pass.

Requirements: 1. Make ONE heap with room for k + 1 values. 2. Go through the array in order. Before inserting each value: when the heap is full, remove its smallest value and write it into the next unfilled slot of the array (slot 0 first, then 1, and so on). 3. After the last value is inserted, remove everything left in the heap into the remaining slots. 4. Destroy the heap before returning.

Do NOT write a main function.

Expected Output:

sorted: 1 2 3 4 5 6 7 8 9
largest heap used: 3

= newline. The output ends with a newline — print one after the last line.

Hints4 available
Topics:
Data Structures & AlgorithmsHeaps
1
Tab to indent (Esc then Tab to move on) · Ctrl+Enter to run · Shift+Alt+F to format · Ctrl+Space to expand shortcuts (p, fori)

Your Output

Run your code to see the output here...

Test Cases

Run your code to see test case results.