1
|
/*
|
2
|
Copyright (c) 2003-2006 Niels Kokholm and Peter Sestoft
|
3
|
Permission is hereby granted, free of charge, to any person obtaining a copy
|
4
|
of this software and associated documentation files (the "Software"), to deal
|
5
|
in the Software without restriction, including without limitation the rights
|
6
|
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
|
7
|
copies of the Software, and to permit persons to whom the Software is
|
8
|
furnished to do so, subject to the following conditions:
|
9
|
|
10
|
The above copyright notice and this permission notice shall be included in
|
11
|
all copies or substantial portions of the Software.
|
12
|
|
13
|
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
|
14
|
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
|
15
|
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
|
16
|
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
|
17
|
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
|
18
|
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
|
19
|
SOFTWARE.
|
20
|
*/
|
21
|
|
22
|
using System;
|
23
|
using C5;
|
24
|
using NUnit.Framework;
|
25
|
using SCG = System.Collections.Generic;
|
26
|
|
27
|
namespace C5UnitTests.SortingTests
|
28
|
{
|
29
|
[TestFixture]
|
30
|
public class SortRandom
|
31
|
{
|
32
|
IC ic;
|
33
|
|
34
|
Random ran;
|
35
|
|
36
|
int[] a;
|
37
|
|
38
|
int length;
|
39
|
|
40
|
|
41
|
[SetUp]
|
42
|
public void Init()
|
43
|
{
|
44
|
ic = new IC();
|
45
|
ran = new Random(3456);
|
46
|
length = 100000;
|
47
|
a = new int[length];
|
48
|
for (int i = 0; i < length; i++)
|
49
|
a[i] = ran.Next();
|
50
|
}
|
51
|
|
52
|
|
53
|
[Test]
|
54
|
public void HeapSort()
|
55
|
{
|
56
|
Sorting.HeapSort<int>(a, 0, length, ic);
|
57
|
for (int i = 1; i < length; i++)
|
58
|
Assert.IsTrue(a[i - 1] <= a[i], "Inversion at " + i);
|
59
|
}
|
60
|
|
61
|
|
62
|
[Test]
|
63
|
public void IntroSort()
|
64
|
{
|
65
|
Sorting.IntroSort<int>(a, 0, length, ic);
|
66
|
for (int i = 1; i < length; i++)
|
67
|
Assert.IsTrue(a[i - 1] <= a[i], "Inversion at " + i);
|
68
|
}
|
69
|
|
70
|
|
71
|
[Test]
|
72
|
public void InsertionSort()
|
73
|
{
|
74
|
length = 1000;
|
75
|
Sorting.InsertionSort<int>(a, 0, length, ic);
|
76
|
for (int i = 1; i < length; i++)
|
77
|
Assert.IsTrue(a[i - 1] <= a[i], "Inversion at " + i);
|
78
|
|
79
|
Sorting.InsertionSort<int>(a, length, 2 * length, ic);
|
80
|
for (int i = length + 1; i < 2 * length; i++)
|
81
|
Assert.IsTrue(a[i - 1] <= a[i], "Inversion at " + i);
|
82
|
}
|
83
|
|
84
|
|
85
|
[TearDown]
|
86
|
public void Dispose() { ic = null; }
|
87
|
}
|
88
|
|
89
|
|
90
|
|
91
|
[TestFixture]
|
92
|
public class SortRandomDuplicates
|
93
|
{
|
94
|
IC ic;
|
95
|
|
96
|
Random ran;
|
97
|
|
98
|
int[] a;
|
99
|
|
100
|
int length;
|
101
|
|
102
|
|
103
|
[SetUp]
|
104
|
public void Init()
|
105
|
{
|
106
|
ic = new IC();
|
107
|
ran = new Random(3456);
|
108
|
length = 100000;
|
109
|
a = new int[length];
|
110
|
for (int i = 0; i < length; i++)
|
111
|
a[i] = ran.Next(3, 23);
|
112
|
}
|
113
|
|
114
|
|
115
|
[Test]
|
116
|
public void HeapSort()
|
117
|
{
|
118
|
Sorting.HeapSort<int>(a, 0, length, ic);
|
119
|
for (int i = 1; i < length; i++)
|
120
|
Assert.IsTrue(a[i - 1] <= a[i], "Inversion at " + i);
|
121
|
}
|
122
|
|
123
|
|
124
|
[Test]
|
125
|
public void IntroSort()
|
126
|
{
|
127
|
Sorting.IntroSort<int>(a, 0, length, ic);
|
128
|
for (int i = 1; i < length; i++)
|
129
|
Assert.IsTrue(a[i - 1] <= a[i], "Inversion at " + i);
|
130
|
}
|
131
|
|
132
|
|
133
|
[Test]
|
134
|
public void InsertionSort()
|
135
|
{
|
136
|
length = 1000;
|
137
|
Sorting.InsertionSort<int>(a, 0, length, ic);
|
138
|
for (int i = 1; i < length; i++)
|
139
|
Assert.IsTrue(a[i - 1] <= a[i], "Inversion at " + i);
|
140
|
|
141
|
Sorting.InsertionSort<int>(a, length, 2 * length, ic);
|
142
|
for (int i = length + 1; i < 2 * length; i++)
|
143
|
Assert.IsTrue(a[i - 1] <= a[i], "Inversion at " + i);
|
144
|
}
|
145
|
|
146
|
|
147
|
[TearDown]
|
148
|
public void Dispose() { ic = null; a = null; ran = null; }
|
149
|
}
|
150
|
|
151
|
|
152
|
|
153
|
[TestFixture]
|
154
|
public class SortIncreasing
|
155
|
{
|
156
|
IC ic;
|
157
|
|
158
|
int[] a;
|
159
|
|
160
|
int length;
|
161
|
|
162
|
|
163
|
[SetUp]
|
164
|
public void Init()
|
165
|
{
|
166
|
ic = new IC();
|
167
|
length = 100000;
|
168
|
a = new int[length];
|
169
|
for (int i = 0; i < length; i++)
|
170
|
a[i] = i;
|
171
|
}
|
172
|
|
173
|
|
174
|
[Test]
|
175
|
public void HeapSort()
|
176
|
{
|
177
|
Sorting.HeapSort<int>(a, 0, length, ic);
|
178
|
for (int i = 1; i < length; i++)
|
179
|
Assert.IsTrue(a[i - 1] <= a[i], "Inversion at " + i);
|
180
|
}
|
181
|
|
182
|
|
183
|
[Test]
|
184
|
public void IntroSort()
|
185
|
{
|
186
|
Sorting.IntroSort<int>(a, 0, length, ic);
|
187
|
for (int i = 1; i < length; i++)
|
188
|
Assert.IsTrue(a[i - 1] <= a[i], "Inversion at " + i);
|
189
|
}
|
190
|
|
191
|
|
192
|
[Test]
|
193
|
public void InsertionSort()
|
194
|
{
|
195
|
length = 1000;
|
196
|
Sorting.InsertionSort<int>(a, 0, length, ic);
|
197
|
for (int i = 1; i < length; i++)
|
198
|
Assert.IsTrue(a[i - 1] <= a[i], "Inversion at " + i);
|
199
|
|
200
|
Sorting.InsertionSort<int>(a, length, 2 * length, ic);
|
201
|
for (int i = length + 1; i < 2 * length; i++)
|
202
|
Assert.IsTrue(a[i - 1] <= a[i], "Inversion at " + i);
|
203
|
}
|
204
|
|
205
|
|
206
|
[TearDown]
|
207
|
public void Dispose() { ic = null; a = null; }
|
208
|
}
|
209
|
|
210
|
|
211
|
|
212
|
[TestFixture]
|
213
|
public class SortDecreasing
|
214
|
{
|
215
|
IC ic;
|
216
|
|
217
|
int[] a;
|
218
|
|
219
|
int length;
|
220
|
|
221
|
|
222
|
[SetUp]
|
223
|
public void Init()
|
224
|
{
|
225
|
ic = new IC();
|
226
|
length = 100000;
|
227
|
a = new int[length];
|
228
|
for (int i = 0; i < length; i++)
|
229
|
a[i] = -i;
|
230
|
}
|
231
|
|
232
|
|
233
|
[Test]
|
234
|
public void HeapSort()
|
235
|
{
|
236
|
Sorting.HeapSort<int>(a, 0, length, ic);
|
237
|
for (int i = 1; i < length; i++)
|
238
|
Assert.IsTrue(a[i - 1] <= a[i], "Inversion at " + i);
|
239
|
}
|
240
|
|
241
|
|
242
|
[Test]
|
243
|
public void IntroSort()
|
244
|
{
|
245
|
Sorting.IntroSort<int>(a, 0, length, ic);
|
246
|
for (int i = 1; i < length; i++)
|
247
|
Assert.IsTrue(a[i - 1] <= a[i], "Inversion at " + i);
|
248
|
}
|
249
|
|
250
|
|
251
|
[Test]
|
252
|
public void InsertionSort()
|
253
|
{
|
254
|
length = 1000;
|
255
|
Sorting.InsertionSort<int>(a, 0, length, ic);
|
256
|
for (int i = 1; i < length; i++)
|
257
|
Assert.IsTrue(a[i - 1] <= a[i], "Inversion at " + i);
|
258
|
|
259
|
Sorting.InsertionSort<int>(a, length, 2 * length, ic);
|
260
|
for (int i = length + 1; i < 2 * length; i++)
|
261
|
Assert.IsTrue(a[i - 1] <= a[i], "Inversion at " + i);
|
262
|
}
|
263
|
|
264
|
|
265
|
[TearDown]
|
266
|
public void Dispose() { ic = null; a = null; }
|
267
|
}
|
268
|
}
|