Differences

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

--- courses:cs211:winter2012:journals:jeanpaul:chapter_fivesection_iii [2012/03/12 21:30] – mugabej
+++ courses:cs211:winter2012:journals:jeanpaul:chapter_fivesection_iii [2012/03/12 22:25] (current) – [Designing and Analyzing the Algorithm] mugabej
@@ Line 20: / Line 20: @@
 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> End if\\
 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Advance the //current// pointer in the list from which the smaller element was selected.\\
->>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> End While
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> 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