Problem:
Recall the Partition subroutine that we used in both QuickSort and RSelect. Suppose that the following array has just been partitioned around some pivot element: 3, 1, 2, 4, 5, 8, 7, 6, 9
Solution:
Any number that can be a pivot must have all left hand side smaller than it and right hand side larger than it, looking at the array, that will be these elements:
3, 1, 2, 4, 5, 8, 7, 6, 9
Therefore the answer is 4, 5, 9. I missed 9 during my own exam, just a careless mistake.
Recall the Partition subroutine that we used in both QuickSort and RSelect. Suppose that the following array has just been partitioned around some pivot element: 3, 1, 2, 4, 5, 8, 7, 6, 9
Solution:
Any number that can be a pivot must have all left hand side smaller than it and right hand side larger than it, looking at the array, that will be these elements:
3, 1, 2, 4, 5, 8, 7, 6, 9
Therefore the answer is 4, 5, 9. I missed 9 during my own exam, just a careless mistake.
No comments:
Post a Comment