-- Feb 27 In-Class Exercise Thread
How many different types sorting subroutines does BoxSort involve?
``
Solution:
- Pick `\sqrt{n}` elements and sort them to be "splitters"
-
Insert the remaining elements between the splitters using binary search. (a rough, partial sort. not a full sort)
- Recurse with BoxSort on subproblems greater than size `\log n`
- Otherwise, use LogSort
Therefore there are three different types sorting subroutines involved in BoxSort (including BoxSort itself!).
For the first of the subtype used to sort `\sqrt{n}` splitter elements, show how would it sort 6,2,8,7? (Show step by step.)
``
Solution: From slides, "To do the sorting we imagine for each `i` of the `\sqrt{n}` many elements of `R`, using `sqrt{n}−1` processors to compare it with the other `\sqrt{n}−1` elements, then using `O(\log n)` time to sum the values of these comparisons to determine the number of elements smaller than `i`."
``
Use 3 processors for each element `i\in\{6, 2, 8, 7\}` to compare to the other elements. A total of 12 processors assign the following values, where each '1' represents being greater than some other element `j\in\{6, 2, 8, 7\}` where `j != i`. We sum the results from all the processors using a `\log`-sized tree in `O(\log n)` time.
Therefore, the sorted order, corresponding to `\{0, 1, 2, 3\}` for the values returned by summing the comparisons from each processor, is `\{2, 6, 7, 8\}`. We use the result of as the array index to place the corresponding splitter.
(
Edited: 2019-02-27)
''How many different types sorting subroutines does BoxSort involve?''
@BT@@BT@
'''Solution:'''
# Pick @BT@\sqrt{n}@BT@ elements and sort them to be "splitters"
# <s>Insert the remaining elements between the splitters using binary search. (a rough, partial sort. not a full sort)</s>
# Recurse with BoxSort on subproblems greater than size @BT@\log n@BT@
# Otherwise, use LogSort
Therefore there are '''three''' different types sorting subroutines involved in BoxSort (including BoxSort itself!).
----
''For the first of the subtype used to sort @BT@\sqrt{n}@BT@ splitter elements, show how would it sort 6,2,8,7? (Show step by step.)
''
@BT@@BT@
'''Solution:''' From slides, "To do the sorting we imagine for each @BT@i@BT@ of the @BT@\sqrt{n}@BT@ many elements of @BT@R@BT@, using @BT@sqrt{n}−1@BT@ processors to compare it with the other @BT@\sqrt{n}−1@BT@ elements, then using @BT@O(\log n)@BT@ time to sum the values of these comparisons to determine the number of elements smaller than @BT@i@BT@."
@BT@@BT@
Use 3 processors for each element @BT@i\in\{6, 2, 8, 7\}@BT@ to compare to the other elements. A total of 12 processors assign the following values, where each '1' represents being greater than some other element @BT@j\in\{6, 2, 8, 7\}@BT@ where @BT@j != i@BT@. We sum the results from all the processors using a @BT@\log@BT@-sized tree in @BT@O(\log n)@BT@ time.
* 6 - 1
* 2 - 0
* 8 - 3
* 7 - 2
Therefore, the sorted order, corresponding to @BT@\{0, 1, 2, 3\}@BT@ for the values returned by summing the comparisons from each processor, is @BT@\{2, 6, 7, 8\}@BT@. We use the result of as the array index to place the corresponding splitter.