1 Show how heapsort processes the sequence 5 13 2 25 7 17 20

1. Show how heapsort processes the sequence 5, 13, 2, 25, 7, 17, 20, 8, 4. Start with heap construction, and then remove the maximum element one at a time. You can either draw a tree or use an array to represent the heap. Mark the sorted part at each step (using color, italic/bold font, circle, etc.).

2.  Sort the sequence 3, 1, 4, 1, 5, 9, 2, 6 using mergesort. Show the divide and merge steps.

3. Sort the sequence 2, 6, 9, 5, 1, 3, 4, 7, 8 using quicksort that selects the middle element as pivot (round down in the case of inputs of even size). Show the state of the array after each recursive level of the quicksort execution, marking the chosen pivot and the sorted part at each step.

Solution

[1]

-------------------------------------------------------------------------------------------------------------------------------------------------------------

[2]
Array to be sorted
3, 1, 4, 1, 5, 9, 2, 6
• Divide array into two halves
3 1 4 1 | 5 9 2 6
• Conquer: Recursively sort each half
1 1 3 4 | 2 5 6 9
• Merge each half into fully sorted array
1 1 2 3 4 5 6 9