Timeline for $O(n\log n)$ algorithm for minimizing number of inversions in leaves of complete binary tree
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 10, 2019 at 18:01 | vote | accept | CommunityBot | ||
| Feb 10, 2019 at 17:28 | comment | added | Yuval Filmus | 1. Right, I'm saying that you can count inversions on the go. Given the inversions inside $L(x_1)$, the inversions inside $L(x_2)$, and the inversions across $L(x_1),L(x_2)$, the sum gives you the inversions inside $L(x)$. 2. You choose whether to switch or not according to the number of inversions across $L(x_1),L(x_2)$, which you can compute as part of your merge procedure. | |
| Feb 10, 2019 at 17:21 | comment | added | user95596 | Just to be clear, 1. Are you saying it's possible to count the inversions of the resulting merged array while doing the merge routine? I don't see how you can know the total number of inversions that will be in the final array when you still have possible swaps to make while merging. 2. Are you also saying that the sums are a valid way of checking which subarray to move left? | |
| Feb 10, 2019 at 17:17 | comment | added | Yuval Filmus | You compute what you call sums during the merge procedure. You'll have to work it out. You don't have to count the inversions afterwards – this information should be available. | |
| Feb 10, 2019 at 17:15 | comment | added | user95596 | I've gotten as far as splitting recursively and then when I merge back up I would merge based on which subarray (left or right) has a smaller sum of its elements. The idea is that the one with the smaller sum would (hopefully?) be best to move to the left since it would result in less inversions. Then once everything is sorted I could run another procedure to count the inversions in the final array I just created. I'm not sure about the summing idea though (how I should know what subarray moves to the left side when merging). I'm also not sure if I can just count inversions while I'm doing it. | |
| Feb 10, 2019 at 15:13 | history | answered | Yuval Filmus | CC BY-SA 4.0 |