Differences

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

--- courses:cs211:winter2018:journals:devlinn:chapter5 [2018/03/12 21:39] – [5.1 A First Recurrence: The Mergesort Algorithm] devlinn
+++ courses:cs211:winter2018:journals:devlinn:chapter5 [2018/03/12 21:51] (current) – devlinn
@@ Line 25: / Line 25: @@
 This algorithm has the following recurrence: //T//(//n//) ≤ 2//T//(//n///2) + //cn//<sup>2</sup>. The running time in this case is //O//(//n//<sup>2</sup>).
+===== 5.3 Counting Inversions =====
+We can apply the divide-and-conquer method to many problems, including counting the number of inversions, which compares rankings and looks at those which are "out of order". Given a list of numbers A, we say that two indices //i// and //j//, where //i// < //j//, form an inversion if //a<sub>i</sub>// and //a<sub>j</sub>// are out of order (//a<sub>i</sub>// > //a<sub>j</sub>//). The Merge-and-Count Algorithm can be used to find the number of inversions given a list which has been divided in half and sorted.Here is the algorithm:
+    Merge-and-Count(A, B)
+        Maintain a Current pointer into each list, initialized to point to the front elements
+        Maintain a variable Count for the number of inversions, initialized to 0
+        While both lists nonempty:
+            Let ai and bj be the elements pointed to by the Current pointer
+            Append the smaller of these two to the output list
+            If bj is the smaller element then
+                Increment Count by the number of elements remaining in A
+            Endif
+            Advance the Current pointer in the list from which the smaller element was selected
+        Endwhile
+        Once one list is empty, append the remainder of the other list to the output
+        Return Count and the merged list
+Merge-and-Count takes //O//(//n//) time. I understand this section very well since we went over it in class very thoroughly. It helps to run through an interactive example. I would rate my understanding an 8.