Monday, August 4, 2014

MergeSort

Problem:

TopCoder Problem Statement - MergeSort

Overview:

Implement Merge Sort, and count the number of comparisons needed to sort an array.

Java Source:
01: /*
02: TopCoder
03: Single Round Match: 151
04: Division: 2 / 1
05: Level: 3 / 2
06: Points: 1000 / 500
07: Description: http://community.topcoder.com/stat?c=problem_statement&pm=1705
08:  */
09: 
10: import java.util.ArrayList;
11: import java.util.List;
12: 
13: public class MergeSort {
14: 
15:     private int numCompares = 0;
16: 
17:     public int howManyComparisons(int[] numbers) {
18: 
19:         // Convert the int[] into a List
20:         List list = new ArrayList(numbers.length);
21: 
22:         for (int i : numbers) {
23:             list.add(i);
24:         }
25: 
26:         mergeSort(list);
27: 
28:         return numCompares;
29:     }
30: 
31:     private List mergeSort(List a) {
32: 
33:         if (a.size() <= 1) { return a; }
34: 
35:         List sb = mergeSort(a.subList(0, a.size() / 2));
36:         List sc = mergeSort(a.subList((a.size() / 2), a.size()));
37: 
38:         return merge(sb, sc);
39:     }
40: 
41:     private List merge(List b, List c) {
42: 
43:         /*
44:          * It's important that new Lists are created here to hold copies of b
45:          * and c. Otherwise, we run the risk of a concurrent modification
46:          * exception when we start removing elements
47:          */
48:         List b1 = new ArrayList<>();
49:         List c1 = new ArrayList<>();
50: 
51:         b1.addAll(b);
52:         c1.addAll(c);
53: 
54:         // We know the final size of the List, might as well provide it.
55:         List a = new ArrayList(b.size() + c.size());
56: 
57:         while (!b1.isEmpty() && !c1.isEmpty()) {
58: 
59:             int x = b1.get(0);
60:             int y = c1.get(0);
61: 
62:             numCompares++;
63:             if (x < y) {
64:                 a.add(b1.remove(0));
65:             } else if (x > y) {
66:                 a.add(c1.remove(0));
67:             } else {
68:                 a.add(b1.remove(0));
69:                 a.add(c1.remove(0));
70:             }
71: 
72:         }
73: 
74:         if (!b1.isEmpty()) { a.addAll(b1); }
75: 
76:         if (!c1.isEmpty()) { a.addAll(c1); }
77: 
78:         return a;
79:     }
80: }
Notes:

Merge sort is a classic algorithm that you should know how to implement. The problem statement outlines exactly what you need to do - making this relatively easy. There is only a few obstacles beyond just doing what the problem asks for.

First, we'll need to convert the int[] into a List. That's done on lines 20-24. Pretty basic stuff.

Then, we'll need to split the array correctly inside mergeSort(). The problem statement describes what to do if the size of the array is odd or oven. We don't need to care about that. The / operation rounds down, so we can just take the list from 0 to (size / 2) and from (size / 2) to size. Lines 35 and 36. Note that the first argument to subList is inclusive, and the second is exclusive. The the first subList will get position 0, but stops just before (size / 2). The second subList starts at (size / 2) and stops at the end.

The biggest potential roadback probably lies at line 69. If you do not make copies of the Lists passed into merge, then you're likely to get a ConcurrentModificationException. This can be frustrating if you don't understand what's going on. When subList is called on lines 35 and 36, you don't get a new List, rather it returns a view into the original list. So both sb and sc are backed by List a. If you modify the elememts in one list - say by removing an element, and then access the other view; an exception will be thrown. The solution is just to copy the given Lists into two new Lists. Then you're free to modify them as you wish.

No comments:

Post a Comment