37 int operator()(int a) { return - a; } |
38 int operator()(int a) { return - a; } |
38 }; |
39 }; |
39 |
40 |
40 int negate(int a) { return - a; } |
41 int negate(int a) { return - a; } |
41 |
42 |
42 |
43 template<class T> |
43 void generateIntSequence(int n, std::vector<int>& data) { |
44 bool isTheSame(T &a, T&b) |
|
45 { |
|
46 typename T::iterator ai=a.begin(); |
|
47 typename T::iterator bi=b.begin(); |
|
48 for(;ai!=a.end()||bi!=b.end();++ai,++bi) |
|
49 if(*ai!=*bi) return false; |
|
50 return ai==a.end()&&bi==b.end(); |
|
51 } |
|
52 |
|
53 template<class T> |
|
54 T listsort(typename T::iterator b, typename T::iterator e) |
|
55 { |
|
56 if(b==e) return T(); |
|
57 typename T::iterator bn=b; |
|
58 if(++bn==e) { |
|
59 T l; |
|
60 l.push_back(*b); |
|
61 return l; |
|
62 } |
|
63 typename T::iterator m=b; |
|
64 bool x=false; |
|
65 for(typename T::iterator i=b;i!=e;++i,x=!x) |
|
66 if(x) ++m; |
|
67 T l1(listsort<T>(b,m)); |
|
68 T l2(listsort<T>(m,e)); |
|
69 T l; |
|
70 while((!l1.empty())&&(!l2.empty())) |
|
71 if(l1.front()<=l2.front()) |
|
72 { |
|
73 l.push_back(l1.front()); |
|
74 l1.pop_front(); |
|
75 } |
|
76 else { |
|
77 l.push_back(l2.front()); |
|
78 l2.pop_front(); |
|
79 } |
|
80 while(!l1.empty()) |
|
81 { |
|
82 l.push_back(l1.front()); |
|
83 l1.pop_front(); |
|
84 } |
|
85 while(!l2.empty()) |
|
86 { |
|
87 l.push_back(l2.front()); |
|
88 l2.pop_front(); |
|
89 } |
|
90 return l; |
|
91 } |
|
92 |
|
93 template<class T> |
|
94 void generateIntSequence(int n, T & data) { |
44 int prime = 9973; |
95 int prime = 9973; |
45 int root = 136, value = 1; |
96 int root = 136, value = 1; |
46 for (int i = 0; i < n; ++i) { |
97 for (int i = 0; i < n; ++i) { |
47 data.push_back(value - prime / 2); |
98 data.push_back(value - prime / 2); |
48 value = (value * root) % prime; |
99 value = (value * root) % prime; |
49 } |
100 } |
50 } |
101 } |
51 |
102 |
52 void generateCharSequence(int n, std::vector<unsigned char>& data) { |
103 template<class T> |
|
104 void generateCharSequence(int n, T & data) { |
53 int prime = 251; |
105 int prime = 251; |
54 int root = 3, value = root; |
106 int root = 3, value = root; |
55 for (int i = 0; i < n; ++i) { |
107 for (int i = 0; i < n; ++i) { |
56 data.push_back(static_cast<unsigned char>(value)); |
108 data.push_back(static_cast<unsigned char>(value)); |
57 value = (value * root) % prime; |
109 value = (value * root) % prime; |
69 radixSort(data2.begin(), data2.end()); |
121 radixSort(data2.begin(), data2.end()); |
70 for (int i = 0; i < n; ++i) { |
122 for (int i = 0; i < n; ++i) { |
71 check(data1[i] == data2[i], "Test failed"); |
123 check(data1[i] == data2[i], "Test failed"); |
72 } |
124 } |
73 |
125 |
74 radixSort(data2.begin(), data2.end(), Negate()); |
126 // radixSort(data2.begin(), data2.end(), Negate()); |
|
127 // for (int i = 0; i < n; ++i) { |
|
128 // check(data1[i] == data2[n - 1 - i], "Test failed"); |
|
129 // } |
|
130 |
|
131 // radixSort(data2.begin(), data2.end(), negate); |
|
132 // for (int i = 0; i < n; ++i) { |
|
133 // check(data1[i] == data2[n - 1 - i], "Test failed"); |
|
134 // } |
|
135 |
|
136 } |
|
137 |
|
138 { |
|
139 std::vector<unsigned char> data1(n); |
|
140 generateCharSequence(n, data1); |
|
141 |
|
142 std::vector<unsigned char> data2(data1); |
|
143 std::sort(data1.begin(), data1.end()); |
|
144 |
|
145 radixSort(data2.begin(), data2.end()); |
|
146 for (int i = 0; i < n; ++i) { |
|
147 check(data1[i] == data2[i], "Test failed"); |
|
148 } |
|
149 |
|
150 } |
|
151 { |
|
152 std::list<int> data1; |
|
153 generateIntSequence(n, data1); |
|
154 |
|
155 std::list<int> data2(listsort<std::list<int> >(data1.begin(), data1.end())); |
|
156 |
|
157 radixSort(data1.begin(), data1.end()); |
|
158 |
|
159 check(isTheSame(data1,data2), "Test failed"); |
|
160 |
|
161 |
|
162 // radixSort(data2.begin(), data2.end(), Negate()); |
|
163 // check(isTheSame(data1,data2), "Test failed"); |
|
164 // for (int i = 0; i < n; ++i) { |
|
165 // check(data1[i] == data2[n - 1 - i], "Test failed"); |
|
166 // } |
|
167 |
|
168 // radixSort(data2.begin(), data2.end(), negate); |
|
169 // for (int i = 0; i < n; ++i) { |
|
170 // check(data1[i] == data2[n - 1 - i], "Test failed"); |
|
171 // } |
|
172 |
|
173 } |
|
174 |
|
175 { |
|
176 std::list<unsigned char> data1(n); |
|
177 generateCharSequence(n, data1); |
|
178 |
|
179 std::list<unsigned char> data2(listsort<std::list<unsigned char> > |
|
180 (data1.begin(), |
|
181 data1.end())); |
|
182 |
|
183 radixSort(data1.begin(), data1.end()); |
|
184 check(isTheSame(data1,data2), "Test failed"); |
|
185 |
|
186 } |
|
187 } |
|
188 |
|
189 |
|
190 void checkStableRadixSort() { |
|
191 { |
|
192 std::vector<int> data1; |
|
193 generateIntSequence(n, data1); |
|
194 |
|
195 std::vector<int> data2(data1); |
|
196 std::sort(data1.begin(), data1.end()); |
|
197 |
|
198 stableRadixSort(data2.begin(), data2.end()); |
|
199 for (int i = 0; i < n; ++i) { |
|
200 check(data1[i] == data2[i], "Test failed"); |
|
201 } |
|
202 |
|
203 stableRadixSort(data2.begin(), data2.end(), Negate()); |
75 for (int i = 0; i < n; ++i) { |
204 for (int i = 0; i < n; ++i) { |
76 check(data1[i] == data2[n - 1 - i], "Test failed"); |
205 check(data1[i] == data2[n - 1 - i], "Test failed"); |
77 } |
206 } |
78 |
207 |
79 radixSort(data2.begin(), data2.end(), negate); |
208 stableRadixSort(data2.begin(), data2.end(), negate); |
80 for (int i = 0; i < n; ++i) { |
209 for (int i = 0; i < n; ++i) { |
81 check(data1[i] == data2[n - 1 - i], "Test failed"); |
210 check(data1[i] == data2[n - 1 - i], "Test failed"); |
82 } |
211 } |
83 |
|
84 } |
212 } |
85 |
213 |
86 { |
214 { |
87 std::vector<unsigned char> data1(n); |
215 std::vector<unsigned char> data1(n); |
88 generateCharSequence(n, data1); |
216 generateCharSequence(n, data1); |
94 for (int i = 0; i < n; ++i) { |
222 for (int i = 0; i < n; ++i) { |
95 check(data1[i] == data2[i], "Test failed"); |
223 check(data1[i] == data2[i], "Test failed"); |
96 } |
224 } |
97 |
225 |
98 } |
226 } |
99 } |
227 { |
100 |
228 std::list<int> data1; |
101 |
229 generateIntSequence(n, data1); |
102 void checkStableRadixSort() { |
230 |
103 { |
231 std::list<int> data2(listsort<std::list<int> >(data1.begin(), |
104 std::vector<int> data1; |
232 data1.end())); |
105 generateIntSequence(n, data1); |
233 stableRadixSort(data1.begin(), data1.end()); |
106 |
234 check(isTheSame(data1,data2), "Test failed"); |
107 std::vector<int> data2(data1); |
235 |
108 std::sort(data1.begin(), data1.end()); |
236 // stableRadixSort(data2.begin(), data2.end(), Negate()); |
109 |
237 // for (int i = 0; i < n; ++i) { |
110 stableRadixSort(data2.begin(), data2.end()); |
238 // check(data1[i] == data2[n - 1 - i], "Test failed"); |
111 for (int i = 0; i < n; ++i) { |
239 // } |
112 check(data1[i] == data2[i], "Test failed"); |
240 |
113 } |
241 // stableRadixSort(data2.begin(), data2.end(), negate); |
114 |
242 // for (int i = 0; i < n; ++i) { |
115 stableRadixSort(data2.begin(), data2.end(), Negate()); |
243 // check(data1[i] == data2[n - 1 - i], "Test failed"); |
116 for (int i = 0; i < n; ++i) { |
244 // } |
117 check(data1[i] == data2[n - 1 - i], "Test failed"); |
245 } |
118 } |
246 |
119 |
247 { |
120 stableRadixSort(data2.begin(), data2.end(), negate); |
248 std::list<unsigned char> data1(n); |
121 for (int i = 0; i < n; ++i) { |
249 generateCharSequence(n, data1); |
122 check(data1[i] == data2[n - 1 - i], "Test failed"); |
250 |
123 } |
251 std::list<unsigned char> data2(listsort<std::list<unsigned char> > |
124 } |
252 (data1.begin(), |
125 |
253 data1.end())); |
126 { |
254 radixSort(data1.begin(), data1.end()); |
127 std::vector<unsigned char> data1(n); |
255 check(isTheSame(data1,data2), "Test failed"); |
128 generateCharSequence(n, data1); |
|
129 |
|
130 std::vector<unsigned char> data2(data1); |
|
131 std::sort(data1.begin(), data1.end()); |
|
132 |
|
133 radixSort(data2.begin(), data2.end()); |
|
134 for (int i = 0; i < n; ++i) { |
|
135 check(data1[i] == data2[i], "Test failed"); |
|
136 } |
|
137 |
256 |
138 } |
257 } |
139 } |
258 } |
140 |
259 |
141 int main() { |
260 int main() { |