## Monday, November 12, 2012

### Marzullo's algorithm - in java

Marzullo's algorithm, invented by Keith Marzullo for his Ph.D. dissertation in 1984, is an agreement algorithm used to select sources for estimating accurate time from a number of noisy time sources. I was working on similar requirement at work and came across the algorithm in Wikipedia. Here is a Java implementation of the algorithm.

```public class MarzulloAlgorithm {

public static void main(String[] args) {
Range r1 = new Range("1",10,40);
Range r2 = new Range("2",30,50);
Range r3 = new Range("3",35,45);
List<range> ranges = new ArrayList<range>();
MarzulloAlgorithm m = new MarzulloAlgorithm();
Range r = m.marzulloAlgorithm(ranges);
}

public Range marzulloAlgorithm (List<range> ranges) {
Range result = null;
int best = 0;
int count = 0;
int beststart = 0;
int bestend = 0;
int i = 0;
String name = "";
List<point> points = new ArrayList<point>();
for(Range r:ranges) {
}
Collections.sort(points,new PointComparator());
for(Point p:points) {
count = count - p.getType();
if(best &lt; count) {
best = count;
beststart = p.getPoint();
if(i&lt;(points.size()-1)) {
bestend = points.get(i+1).getPoint();
name = p.getName() + "," + points.get(i+1).getName();
}
}
i++;
}
result = new Range(name,beststart,bestend);
return(result);
}
}
```

I have added some data structures like Range and Point for my purpose at work. Definition for Range and Point below.

```public class Point {
String name;
int point;
int type;

public Point(String name, int point, int type) {
this.name = name;
this.point = point;
this.type = type;
}

public String getName() {
return name;
}
public int getPoint() {
return point;
}
public int getType() {
return type;
}
}
```
```public class Range {
String name;
int start;
int end;

public Range(String name, int start, int end) {
this.name = name;
this.start = start;
this.end = end;
}

public String getName() {
return name;
}

public int getStart() {
return start;
}

public int getEnd() {
return end;
}
}
```

1. 2. 