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
|
using System;
|
22
|
using System.Diagnostics;
|
23
|
using SCG = System.Collections.Generic;
|
24
|
namespace C5
|
25
|
{
|
26
|
/// <summary>
|
27
|
/// A utility class with functions for sorting arrays with respect to an IComparer<T>
|
28
|
/// </summary>
|
29
|
public class Sorting
|
30
|
{
|
31
|
Sorting() { }
|
32
|
|
33
|
/// <summary>
|
34
|
/// Sort part of array in place using IntroSort
|
35
|
/// </summary>
|
36
|
/// <exception cref="ArgumentOutOfRangeException">If the <code>start</code>
|
37
|
/// and <code>count</code> arguments does not describe a valid range.</exception>
|
38
|
/// <param name="array">Array to sort</param>
|
39
|
/// <param name="start">Index of first position to sort</param>
|
40
|
/// <param name="count">Number of elements to sort</param>
|
41
|
/// <param name="comparer">IComparer<T> to sort by</param>
|
42
|
[Tested]
|
43
|
public static void IntroSort<T>(T[] array, int start, int count, SCG.IComparer<T> comparer)
|
44
|
{
|
45
|
if (start < 0 || count < 0 || start + count > array.Length)
|
46
|
throw new ArgumentOutOfRangeException();
|
47
|
new Sorter<T>(array, comparer).IntroSort(start, start + count);
|
48
|
}
|
49
|
|
50
|
/// <summary>
|
51
|
/// Sort an array in place using IntroSort and default comparer
|
52
|
/// </summary>
|
53
|
/// <exception cref="NotComparableException">If T is not comparable</exception>
|
54
|
/// <param name="array">Array to sort</param>
|
55
|
[Tested]
|
56
|
public static void IntroSort<T>(T[] array)
|
57
|
{
|
58
|
new Sorter<T>(array, Comparer<T>.Default).IntroSort(0, array.Length);
|
59
|
}
|
60
|
|
61
|
|
62
|
/// <summary>
|
63
|
/// Sort part of array in place using Insertion Sort
|
64
|
/// </summary>
|
65
|
/// <exception cref="ArgumentOutOfRangeException">If the <code>start</code>
|
66
|
/// and <code>count</code> arguments does not describe a valid range.</exception>
|
67
|
/// <param name="array">Array to sort</param>
|
68
|
/// <param name="start">Index of first position to sort</param>
|
69
|
/// <param name="count">Number of elements to sort</param>
|
70
|
/// <param name="comparer">IComparer<T> to sort by</param>
|
71
|
[Tested]
|
72
|
public static void InsertionSort<T>(T[] array, int start, int count, SCG.IComparer<T> comparer)
|
73
|
{
|
74
|
if (start < 0 || count < 0 || start + count > array.Length)
|
75
|
throw new ArgumentOutOfRangeException();
|
76
|
new Sorter<T>(array, comparer).InsertionSort(start, start + count);
|
77
|
}
|
78
|
|
79
|
|
80
|
/// <summary>
|
81
|
/// Sort part of array in place using Heap Sort
|
82
|
/// </summary>
|
83
|
/// <exception cref="ArgumentOutOfRangeException">If the <code>start</code>
|
84
|
/// and <code>count</code> arguments does not describe a valid range.</exception>
|
85
|
/// <param name="array">Array to sort</param>
|
86
|
/// <param name="start">Index of first position to sort</param>
|
87
|
/// <param name="count">Number of elements to sort</param>
|
88
|
/// <param name="comparer">IComparer<T> to sort by</param>
|
89
|
[Tested]
|
90
|
public static void HeapSort<T>(T[] array, int start, int count, SCG.IComparer<T> comparer)
|
91
|
{
|
92
|
if (start < 0 || count < 0 || start + count > array.Length)
|
93
|
throw new ArgumentOutOfRangeException();
|
94
|
new Sorter<T>(array, comparer).HeapSort(start, start + count);
|
95
|
}
|
96
|
|
97
|
|
98
|
class Sorter<T>
|
99
|
{
|
100
|
T[] a;
|
101
|
|
102
|
SCG.IComparer<T> c;
|
103
|
|
104
|
|
105
|
internal Sorter(T[] a, SCG.IComparer<T> c) { this.a = a; this.c = c; }
|
106
|
|
107
|
|
108
|
internal void IntroSort(int f, int b)
|
109
|
{
|
110
|
if (b - f > 31)
|
111
|
{
|
112
|
int depth_limit = (int)Math.Floor(2.5 * Math.Log(b - f, 2));
|
113
|
|
114
|
introSort(f, b, depth_limit);
|
115
|
}
|
116
|
else
|
117
|
InsertionSort(f, b);
|
118
|
}
|
119
|
|
120
|
|
121
|
private void introSort(int f, int b, int depth_limit)
|
122
|
{
|
123
|
const int size_threshold = 14;//24;
|
124
|
|
125
|
if (depth_limit-- == 0)
|
126
|
HeapSort(f, b);
|
127
|
else if (b - f <= size_threshold)
|
128
|
InsertionSort(f, b);
|
129
|
else
|
130
|
{
|
131
|
int p = partition(f, b);
|
132
|
|
133
|
introSort(f, p, depth_limit);
|
134
|
introSort(p, b, depth_limit);
|
135
|
}
|
136
|
}
|
137
|
|
138
|
|
139
|
private int compare(T i1, T i2) { return c.Compare(i1, i2); }
|
140
|
|
141
|
|
142
|
private int partition(int f, int b)
|
143
|
{
|
144
|
int bot = f, mid = (b + f) / 2, top = b - 1;
|
145
|
T abot = a[bot], amid = a[mid], atop = a[top];
|
146
|
|
147
|
if (compare(abot, amid) < 0)
|
148
|
{
|
149
|
if (compare(atop, abot) < 0)//atop<abot<amid
|
150
|
{ a[top] = amid; amid = a[mid] = abot; a[bot] = atop; }
|
151
|
else if (compare(atop, amid) < 0) //abot<=atop<amid
|
152
|
{ a[top] = amid; amid = a[mid] = atop; }
|
153
|
//else abot<amid<=atop
|
154
|
}
|
155
|
else
|
156
|
{
|
157
|
if (compare(amid, atop) > 0) //atop<amid<=abot
|
158
|
{ a[bot] = atop; a[top] = abot; }
|
159
|
else if (compare(abot, atop) > 0) //amid<=atop<abot
|
160
|
{ a[bot] = amid; amid = a[mid] = atop; a[top] = abot; }
|
161
|
else //amid<=abot<=atop
|
162
|
{ a[bot] = amid; amid = a[mid] = abot; }
|
163
|
}
|
164
|
|
165
|
int i = bot, j = top;
|
166
|
|
167
|
while (true)
|
168
|
{
|
169
|
while (compare(a[++i], amid) < 0) ;
|
170
|
|
171
|
while (compare(amid, a[--j]) < 0) ;
|
172
|
|
173
|
if (i < j)
|
174
|
{
|
175
|
T tmp = a[i]; a[i] = a[j]; a[j] = tmp;
|
176
|
}
|
177
|
else
|
178
|
return i;
|
179
|
}
|
180
|
}
|
181
|
|
182
|
|
183
|
internal void InsertionSort(int f, int b)
|
184
|
{
|
185
|
for (int j = f + 1; j < b; j++)
|
186
|
{
|
187
|
T key = a[j], other;
|
188
|
int i = j - 1;
|
189
|
|
190
|
if (c.Compare(other = a[i], key) > 0)
|
191
|
{
|
192
|
a[j] = other;
|
193
|
while (i > f && c.Compare(other = a[i - 1], key) > 0) { a[i--] = other; }
|
194
|
|
195
|
a[i] = key;
|
196
|
}
|
197
|
}
|
198
|
}
|
199
|
|
200
|
|
201
|
internal void HeapSort(int f, int b)
|
202
|
{
|
203
|
for (int i = (b + f) / 2; i >= f; i--) heapify(f, b, i);
|
204
|
|
205
|
for (int i = b - 1; i > f; i--)
|
206
|
{
|
207
|
T tmp = a[f]; a[f] = a[i]; a[i] = tmp;
|
208
|
heapify(f, i, f);
|
209
|
}
|
210
|
}
|
211
|
|
212
|
|
213
|
private void heapify(int f, int b, int i)
|
214
|
{
|
215
|
T pv = a[i], lv, rv, max = pv;
|
216
|
int j = i, maxpt = j;
|
217
|
|
218
|
while (true)
|
219
|
{
|
220
|
int l = 2 * j - f + 1, r = l + 1;
|
221
|
|
222
|
if (l < b && compare(lv = a[l], max) > 0) { maxpt = l; max = lv; }
|
223
|
|
224
|
if (r < b && compare(rv = a[r], max) > 0) { maxpt = r; max = rv; }
|
225
|
|
226
|
if (maxpt == j)
|
227
|
break;
|
228
|
|
229
|
a[j] = max;
|
230
|
max = pv;
|
231
|
j = maxpt;
|
232
|
}
|
233
|
|
234
|
if (j > i)
|
235
|
a[j] = pv;
|
236
|
}
|
237
|
}
|
238
|
}
|
239
|
}
|