Differences

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

--- courses:cs211:winter2018:journals:donohuem:chapter5 [2018/03/12 21:17] – donohuem
+++ courses:cs211:winter2018:journals:donohuem:chapter5 [2018/03/12 21:39] (current) – [5.3 Counting Inversions] donohuem
@@ Line 12: / Line 12: @@
 ===== 5.3 Counting Inversions =====
+The motivation of the problem is preference rankings. Suppose we wish to create an algorithm that compares the rankings of one individual to another's. Similar rankings have very little differences, and different rankings have, obviously, a great deal of differences. In this sense, when comparing two rankings we wish to count the number of inversions as an indication of how similar/different the two rankings are. An algorithm that performs this type of comparison can run in O(nlogn) time. This algorithm makes use of a routine called Merge-and-Count, which takes two sorted lists A and B and both simultaneously adds elements from A and B into a combined sorted list C and counts the number of inversions. This itself takes O(n) time but is only one part of the overall algorithm.
+  Sort-and-Count(L)
+   if list L has one element
+    return 0 and the list L
+   Divide the list into two halves A and B
+   (iA, A) = Sort-and-Count(A)
+   (iB, B) = Sort-and-Count(B)
+   (i, L) = Merge-and-Count(A, B)
+   total_inversions = iA + iB + i
+   return total_inversions and the sorted list L
+Overall, the readability of this section is 7/10.