Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |||
| courses:cs211:winter2018:journals:boyese:chapter5 [2018/03/12 18:51] – [Section 5.3: Counting Inversions] boyese | courses:cs211:winter2018:journals:boyese:chapter5 [2018/03/12 19:29] (current) – [Section 5.3: Counting Inversions] boyese | ||
|---|---|---|---|
| Line 52: | Line 52: | ||
| ====Section 5.3: Counting Inversions==== | ====Section 5.3: Counting Inversions==== | ||
| + | |||
| + | **Comparing rankings** | ||
| + | * To determine similarity of rankings we need a metric | ||
| + | * Similarity metric: number of inversions between two rankings | ||
| + | * My rank: 1, 2, …, n | ||
| + | * Your rank: a< | ||
| + | * Indices i and j are inverted if i < j but a< | ||
| + | * Geometric series | ||
| + | |||
| + | **Brute force solution** | ||
| + | * Look at every pair (i, j) and determine if they are an inversion | ||
| + | * Requires Θ(n< | ||
| + | * Note: already an efficient algorithm but we can try to improve on run time | ||
| + | |||
| + | **Divide and conquer** | ||
| + | * Assume number represents where item should be in the list, i.e., where it is in someone else’s list | ||
| + | * Divide: separate list into two pieces | ||
| + | * Conquer: recursively count inversions in each half | ||
| + | * Combine: count inversions where ai and aj are in different halves, and return sum of three quantities | ||
| + | |||
| + | |||
| + | //Merging two sorted lists while also counting the number of inversions between them.// | ||
| < | < | ||
| Line 68: | Line 90: | ||
| Return Count and the merged list | Return Count and the merged list | ||
| </ | </ | ||
| + | |||
| + | //The Sort-and-Count algorithm correctly sorts the input list and counts the number of inversions; it runs in O(n log n) time for a list with n elements.// | ||
| < | < | ||
