Differences

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

--- courses:cs211:winter2018:journals:ahmadh:ch5 [2018/03/11 08:39] – ahmadh
+++ courses:cs211:winter2018:journals:ahmadh:ch5 [2018/03/13 02:48] (current) – ahmadh
@@ Line 76: / Line 76: @@
 Consider the following algorithm:
-	Merge-and-Count(A,B)
+	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
@@ Line 89: / Line 89: @@
 	   Once one list is empty, append the remainder of the other list to the output
 	   Return Count and the merged list
+Each iteration of the While loop takes constant time, and in each iteration we add some element to the output that will never be seen again. Thus the number of iterations can be at most the sum of the initial lengths of A and B, and so the total running time is O(n).
+We use this Merge-and-Count routine in a recursive procedure that simultaneously sorts and counts the number of inversions in a list L.
+	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] elements
+	       B contains the remaining [n/2] elements
+	      (r_A, A) = Sort-and-Count(A)
+	      (r_B, B) = Sort-and-Count(B)
+	      (r, L) = Merge-and-Count(A, B)
+	   Endif
+	   Return r = r_A + r_B + r, and the sorted list L
+Since our Merge-and-Count procedure takes O(n) time, the rimming time T(n) of the full Sort-and-Count procedure satisfies the recurrence (5.1). Therefore, the Sort-and-Count algorithm correctly sorts the input list and counts the number of inversions, and runs in O(n log n) time for a list with n elements.
+==== 5.3.2 Comments ====
+I feel like this was one of the sections where class discussion was very important. Just reading the algorithm alone did not make much sense to mean, and I struggled understanding the key reason why the algorithm returns a sorted list along with the count. It did not seem necessary to me when I was reading this section before--however, after class discussion on Monday, the algorithm made a whole lot more sense. I think sorting the lists and comparing them to find inversions was an ingenious idea. This felt like it was one of the more interesting ones--8/10.