Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| courses:cs211:winter2018:journals:nasona:chapter5 [2018/03/11 20:39] – [5.3 Counting Inversions] nasona | courses:cs211:winter2018:journals:nasona:chapter5 [2018/03/11 22:21] (current) – [5.3 Counting Inversions] nasona | ||
|---|---|---|---|
| Line 2: | Line 2: | ||
| ==Summary== | ==Summary== | ||
| + | Mergesort sorts a list by dividing it into two equal parts, sorting each half by recursion, then combining resulting sorted components. The recurrence relation for mergesort is T(n) <= 2T(n/2) + cn when n>2 and T(2) <= c. There are two ways to solve the recurrence relation: unrolling the recursion and substituting a solution. Unrolling the recurrence includes analyzing the first few levels, identifying a level pattern, and sum over all levels of recursive calls. Substituting requires you to is where you guess the solution, substitute it in, and prove that it works. The total runtime of mergesort is O(nlogn). | ||
| + | |||
| ==Mergesort== | ==Mergesort== | ||
| Line 49: | Line 51: | ||
| ==Summary== | ==Summary== | ||
| + | Now, we need to consider divide and conquer algorithms that create recursive calls on q subproblems of size n/2 and comibine the results in linear time. We already handled when q=2 with mergesort. When q > 2, the recurrence relation is T(n) <= qT(n/2) + cn when n > 2 and T(2) <=c. By unrolling the recursion, we come to the conclusion that the runtime of the algorithm is O(n^(log2q)). When q = 1, by unrolling the recurrence, we get that T(n) <= 2cn = O(n). A related recurrence of T(n) < | ||
| ==The Case of q>2 Subproblems== | ==The Case of q>2 Subproblems== | ||
| Line 110: | Line 113: | ||
| ==Summary== | ==Summary== | ||
| + | We want to be able to tell how far away a list is from being in order. In order to do this, we just have to count the number of inversions. The brute force solution to the algorithm runs in O(n^2) time, but we can do better than that. We will divide the list in half, count the number of inversions in each piece, and make the algorithm recursively sort the two halves. Once we get the two sorted halves, we want to combine them into a single sorted list while counting the number of inversions as we go. The Merge-and-Count routine takes O(n) time and the Sort-and-Count algorithm takes a total O(nlogn) time. | ||
| ==The Problem== | ==The Problem== | ||
