Differences

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

--- courses:cs211:winter2018:journals:boyese:chapter5 [2018/03/12 18:43] – [Section 5.2: Further Recurrence Relations] boyese
+++ courses:cs211:winter2018:journals:boyese:chapter5 [2018/03/12 19:29] (current) – [Section 5.3: Counting Inversions] boyese
@@ Line 52: / Line 52: @@
 ====Section 5.3: Counting Inversions====
+**Comparing rankings**
+  * To determine similarity of rankings we need a metric
+  * Similarity metric: number of inversions between two rankings
+      * My rank: 1, 2, …, n
+      * Your rank: a<sub>1</sub>, a<sub>2</sub>, …, a<sub>n</sub>
+      * Indices i and j are inverted if i < j but a<sub>i</sub> > a<sub>j</sub>
+      * Geometric series
+**Brute force solution**
+  * Look at every pair (i, j) and determine if they are an inversion
+  * Requires Θ(n<sub>2</sub>) time
+      * Note: already an efficient algorithm but we can try to improve on run time
+**Divide and conquer**
+  * Assume number represents where item should be in the list, i.e., where it is in someone else’s list
+  * Divide: separate list into two pieces
+  * Conquer: recursively count inversions in each half
+  * Combine: count inversions where ai and aj are in different halves, and return sum of three quantities
+//Merging two sorted lists while also counting the number of inversions between them.//
+<code>
+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 are nonempty:
+        Let a<sub>i</sub> and b<sub>j</sub> be the elements pointed to by the Cuwent pointer
+        Append the smaller of these two to the output list
+        If b<sub>j</sub> 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
+</code>
+//The Sort-and-Count algorithm correctly sorts the input list and counts the number of inversions; it runs in O(n log n) time for a list with n elements.//
+<code>
+Sort-and-Count(L)
+    If the list has one element then there are no inversions
+    Else
+        Divide the list into two halves:
+            A contains the first [n/2](ceiling) elements
+            B contains the remaining [n/2](floor) elements
+        (r<sub>A</sub>, A) = Sort-and-Count (A)
+        (r<sub>B</sub>, B) = Sort-and-Count (B)
+        (r, L) = Merge-and-Count (A, B)
+    Endif
+    Return r = r<sub>A</sub> + r<sub>B</sub> + r, and the sorted list L
+</code>