forked from JCarlosR/Sorting-Algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathTournamentSort.java
More file actions
145 lines (122 loc) · 4.45 KB
/
TournamentSort.java
File metadata and controls
145 lines (122 loc) · 4.45 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Random;
class TournamentSort<T> {
T[] array;
private Comparator<T> comparator;
private int[] matches;
private int tourney;
private TournamentSort(Comparator<T> comparator, T[] v) {
this.array = v;
this.matches = new int[6 * v.length];
this.comparator = comparator;
this.tourney = knockout(0, v.length - 1, 3);
}
public static <T> void sort(T[] v, Comparator<T> comparator) {
TournamentSort<T> tourney = new TournamentSort<>(comparator, v);
ArrayList<T> copy = new ArrayList<>(v.length);
for (T ignored : v) copy.add(tourney.pop());
copy.toArray(v);
}
private static Integer[] randomInts(int n) {
Random r = new Random(12345678);
Integer[] v = new Integer[n];
for (int i = 0; i < n; i++)
v[i] = r.nextInt(10 * n);
return v;
}
private static void time(String description, Runnable action, InstrumentedCompare compare) {
long start = System.currentTimeMillis();
action.run();
long finish = System.currentTimeMillis();
System.out.println(description + " took " + ((double) (finish - start) / 1000.0) + " secs " + compare.count + " comparisons");
}
public static void main(String[] args) {
int n = args.length >= 1 ? Integer.parseInt(args[0]) : 100000;
final InstrumentedCompare tournamentCompare = new InstrumentedCompare();
final Integer[] nums = randomInts(n);
time("Tournament.sort", () -> TournamentSort.sort(nums, tournamentCompare), tournamentCompare);
final Integer[] nums2 = randomInts(n);
final InstrumentedCompare systemCompare = new InstrumentedCompare();
time("Array.sort", () -> Arrays.sort(nums2, systemCompare), systemCompare);
for (int i = 0; i < n; i++)
if (nums[i].compareTo(nums2[i]) != 0) {
System.err.println("Arrays do not match at index: " + i);
return;
}
}
private T pop() {
T result = array[getPlayer(tourney)];
tourney = isPlayer(tourney) ? 0 : rebuild(tourney);
return result;
}
private int getPlayer(int i) {
return i <= 0 ? Math.abs(i) : getWinner(i);
}
private void setWinner(int root, int winner) {
matches[root] = winner;
}
private void setWinners(int root, int winners) {
matches[root + 1] = winners;
}
private void setLosers(int root, int losers) {
matches[root + 2] = losers;
}
private int getWinner(int root) {
return matches[root];
}
private int getWinners(int root) {
return matches[root + 1];
}
private int getLosers(int root) {
return matches[root + 2];
}
private void setMatch(int root, int winner, int winners, int losers) {
matches[root] = winner;
matches[root + 1] = winners;
matches[root + 2] = losers;
}
private int mkMatch(int top, int bot, int root) {
int top_w = getPlayer(top);
int bot_w = getPlayer(bot);
if (comparator.compare(array[top_w], array[bot_w]) <= 0)
setMatch(root, top_w, top, bot);
else
setMatch(root, bot_w, bot, top);
return root;
}
private int mkPlayer(int i) {
return -i;
}
private int knockout(int i, int k, int root) {
if (i == k) return mkPlayer(i);
int j = (i + k) / 2;
return mkMatch(knockout(i, j, 2 * root), knockout(j + 1, k, 2 * root + 3), root);
}
private boolean isPlayer(int i) {
return i <= 0;
}
private int rebuild(int root) {
if (isPlayer(getWinners(root)))
return getLosers(root);
else {
setWinners(root, rebuild(getWinners(root)));
if (comparator.compare(array[getPlayer(getLosers(root))], array[getPlayer(getWinners(root))]) < 0) {
setWinner(root, getPlayer(getLosers(root)));
int temp = getLosers(root);
setLosers(root, getWinners(root));
setWinners(root, temp);
} else
setWinner(root, getPlayer(getWinners(root)));
return root;
}
}
static class InstrumentedCompare implements Comparator<Integer> {
int count = 0;
public int compare(Integer a, Integer b) {
count++;
return a.compareTo(b);
}
}
}