Differences

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

--- courses:cs211:winter2012:journals:jeanpaul:chapter_fivesection_iii [2012/03/12 05:10] – created mugabej
+++ courses:cs211:winter2012:journals:jeanpaul:chapter_fivesection_iii [2012/03/12 22:25] (current) – [Designing and Analyzing the Algorithm] mugabej
@@ Line 1: / Line 1: @@
 ====== 5.3 Counting Inversions ======
+\\
+Counting inversions is a problem that we face when analyzing rankings in several applications. The main challenge in this category of problems is to find a way to efficiently compare the rankings.\\
+Let's suppose we have a sequence of n numbers a<sub>1</sub>,a<sub>2</sub>,a<sub>3</sub>,...,a<sub>n</sub>, assuming that all the numbers are different. Our concern is to find a measure that tells us how far this sequence is from being in ascending order. The value of that measure should be 0 if the list is sorted and should increase as the list gets more scrambled. Two indices i<j are inverted if a<sub>i</sub> > a<sub>j</sub>j, this means that a<sub>i</sub> appears after a<sub>j</sub> even though i<j.\\
+\\
+=====  Designing and Analyzing the Algorithm =====
+Looking at every pair of numbers would take us O(n²) time.Our aim is to solve the problem in O(nlogn) time.So the algorithm we choose can not look at each inversion individually. \\
+\\
+Algorithm
+Divide the problem into two lists
+>>>>>>>>>>>>>>>>>>>>>>>> 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 not empty:\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Let a<sub>i</sub> and b<sub>j</sub> be the elements pointed to by the //current// pointer.\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Append the smaller of the 2 elements above to the output list\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> If b<sub>j</sub> is the smaller element:\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Increment //Count// by the number of elements remaining in A.\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> End if\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Advance the //current// pointer in the list from which the smaller element was selected.\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> End While\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Once one list is empty, append the remainder of the list to the output\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Return //Count// and the merged list.\\
+\\
+The total running time of this algorithm is O(n) time.For solving the problem,we simultaneously sort and count as follows:\\
+\\
+>>>>>>>>>>>>>>>>>>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\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> (i<sub>A</sub>, A) = Sort-and-Count(A)\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> (i<sub>B</sub>, B) = Sort-and-Count(B)\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> (i, L) = Merge-and-Count(A, B)\\
+>>>>>>>>>>>>>>>>>>>>>>>>> return i = i<sub>A</sub> + i<sub>B</sub> + i and the sorted list L\\
+\\
+For a list with n elements, the overall running time is O(nlogn). \\
+I give this section 8/10