1. Show how heapsort processes the sequence 5, 13, 2, 25, 7, 17, 20, 8, 4. Start
ID: 3938446 • Letter: 1
Question
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.
Explanation / Answer
[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
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.