Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2018:journals:mccaffreyk:home:5 [2018/03/11 22:51] – mccaffreyk
+++ courses:cs211:winter2018:journals:mccaffreyk:home:5 [2018/03/11 23:58] (current) – mccaffreyk
@@ Line 15: / Line 15: @@
 ==== Section 5.3: Counting Inversions ====
-Here, we apply the building blocks from other sections to solve several other recurrence related problems. For instance, we want a way to compute the number of inversions required to transform one into another with the same values but in a different order. Complete agreement between two sets means no inversions are required to make them match and complete disagreement means that the maximum number of inversions are needed(n/2).
+Here, we apply the building blocks from other sections to solve several other recurrence related problems. For instance, we want a way to compute the number of inversions required to transform one into another with the same values but in a different order. Complete agreement between two sets means no inversions are required to make them match and complete disagreement means that the maximum number of inversions are needed(n/2). For the algorithm, suppose that we have 2 sets: A and B where A!=B where the components in A and B are the same. We can split set B int two halves a and b recursively as in typical merge sort. Then, we sort them so that they "match" the order in set A. Finally, we merge a and b so that A==B. To do this, we take from the beginning of a and the end of b each time. This allows us to infer how many inversions we will need in only O(n) time. All along, we keep track of the total number of inversions required. This algorithm runs in O(nlogn) time as does merge sort. A brute force search for inversions would require O(n^2) time.