35 void checkRadixSort() { |
35 void checkRadixSort() { |
36 { |
36 { |
37 int n = 10000; |
37 int n = 10000; |
38 vector<int> data1(n), data2(n); |
38 vector<int> data1(n), data2(n); |
39 for (int i = 0; i < n; ++i) { |
39 for (int i = 0; i < n; ++i) { |
40 data1[i] = data2[i] = (int)(1000 * (rand() / (RAND_MAX + 1.0))) - 500; |
40 data1[i] = data2[i] = rnd[1000] - 500; |
41 } |
41 } |
42 radixSort(data1.begin(), data1.end()); |
42 radixSort(data1.begin(), data1.end()); |
43 sort(data2.begin(), data2.end()); |
43 sort(data2.begin(), data2.end()); |
44 for (int i = 0; i < n; ++i) { |
44 for (int i = 0; i < n; ++i) { |
45 check(data1[i] == data2[i], "Test failed"); |
45 check(data1[i] == data2[i], "Test failed"); |
46 } |
46 } |
47 } { |
47 } { |
48 int n = 10000; |
48 int n = 10000; |
49 vector<unsigned char> data1(n), data2(n); |
49 vector<unsigned char> data1(n), data2(n); |
50 for (int i = 0; i < n; ++i) { |
50 for (int i = 0; i < n; ++i) { |
51 data1[i] = data2[i] = (int)(200 * (rand() / (RAND_MAX + 1.0))); |
51 data1[i] = data2[i] = rnd[(unsigned char)200]; |
52 } |
52 } |
53 radixSort(data1.begin(), data1.end()); |
53 radixSort(data1.begin(), data1.end()); |
54 sort(data2.begin(), data2.end()); |
54 sort(data2.begin(), data2.end()); |
55 for (int i = 0; i < n; ++i) { |
55 for (int i = 0; i < n; ++i) { |
56 check(data1[i] == data2[i], "Test failed"); |
56 check(data1[i] == data2[i], "Test failed"); |
62 void checkCounterSort() { |
62 void checkCounterSort() { |
63 { |
63 { |
64 int n = 10000; |
64 int n = 10000; |
65 vector<int> data1(n), data2(n); |
65 vector<int> data1(n), data2(n); |
66 for (int i = 0; i < n; ++i) { |
66 for (int i = 0; i < n; ++i) { |
67 data1[i] = data2[i] = (int)(1000 * (rand() / (RAND_MAX + 1.0))) - 500; |
67 data1[i] = data2[i] = rnd[1000] - 500; |
68 } |
68 } |
69 counterSort(data1.begin(), data1.end()); |
69 counterSort(data1.begin(), data1.end()); |
70 sort(data2.begin(), data2.end()); |
70 sort(data2.begin(), data2.end()); |
71 for (int i = 0; i < n; ++i) { |
71 for (int i = 0; i < n; ++i) { |
72 check(data1[i] == data2[i], "Test failed"); |
72 check(data1[i] == data2[i], "Test failed"); |
73 } |
73 } |
74 } { |
74 } { |
75 int n = 10000; |
75 int n = 10000; |
76 vector<unsigned char> data1(n), data2(n); |
76 vector<unsigned char> data1(n), data2(n); |
77 for (int i = 0; i < n; ++i) { |
77 for (int i = 0; i < n; ++i) { |
78 data1[i] = data2[i] = (int)(200 * (rand() / (RAND_MAX + 1.0))); |
78 data1[i] = data2[i] = rnd[(unsigned char)200]; |
79 } |
79 } |
80 counterSort(data1.begin(), data1.end()); |
80 counterSort(data1.begin(), data1.end()); |
81 sort(data2.begin(), data2.end()); |
81 sort(data2.begin(), data2.end()); |
82 for (int i = 0; i < n; ++i) { |
82 for (int i = 0; i < n; ++i) { |
83 check(data1[i] == data2[i], "Test failed"); |
83 check(data1[i] == data2[i], "Test failed"); |
104 for (int i = 0; i < n; ++i) { |
104 for (int i = 0; i < n; ++i) { |
105 nodes.push_back(graph.addNode()); |
105 nodes.push_back(graph.addNode()); |
106 } |
106 } |
107 vector<Edge> edges; |
107 vector<Edge> edges; |
108 for (int i = 0; i < e; ++i) { |
108 for (int i = 0; i < e; ++i) { |
109 int s = (int)(n * (double)rand() / (RAND_MAX + 1.0)); |
109 int s = rnd[n]; |
110 int t = (int)(n * (double)rand() / (RAND_MAX + 1.0)); |
110 int t = rnd[n]; |
111 edges.push_back(graph.addEdge(nodes[s], nodes[t])); |
111 edges.push_back(graph.addEdge(nodes[s], nodes[t])); |
112 } |
112 } |
113 |
113 |
114 radixSort(edges.begin(), edges.end(), |
114 radixSort(edges.begin(), edges.end(), |
115 mapFunctor(composeMap(IdMap<Graph, Node>(graph), |
115 mapFunctor(composeMap(IdMap<Graph, Node>(graph), |
143 for (int i = 0; i < n; ++i) { |
143 for (int i = 0; i < n; ++i) { |
144 nodes.push_back(graph.addNode()); |
144 nodes.push_back(graph.addNode()); |
145 } |
145 } |
146 vector<Edge> edges; |
146 vector<Edge> edges; |
147 for (int i = 0; i < e; ++i) { |
147 for (int i = 0; i < e; ++i) { |
148 int s = (int)(n * (double)rand() / (RAND_MAX + 1.0)); |
148 int s = rnd[n]; |
149 int t = (int)(n * (double)rand() / (RAND_MAX + 1.0)); |
149 int t = rnd[n]; |
150 edges.push_back(graph.addEdge(nodes[s], nodes[t])); |
150 edges.push_back(graph.addEdge(nodes[s], nodes[t])); |
151 } |
151 } |
152 |
152 |
153 counterSort(edges.begin(), edges.end(), |
153 counterSort(edges.begin(), edges.end(), |
154 mapFunctor(composeMap(IdMap<Graph, Node>(graph), |
154 mapFunctor(composeMap(IdMap<Graph, Node>(graph), |