| | | 1 | | namespace Towel; |
| | | 2 | | |
| | | 3 | | /// <summary>Root type of the static functional methods in Towel.</summary> |
| | | 4 | | public static partial class Statics |
| | | 5 | | { |
| | | 6 | | #region Reverse |
| | | 7 | | |
| | | 8 | | /// <inheritdoc cref="Reverse{T, TGet, TSet}(int, int, TGet, TSet)"/> |
| | | 9 | | public static void Reverse<T>(int start, int end, Func<int, T> get, Action<int, T> set) => |
| | 34 | 10 | | Reverse<T, SFunc<int, T>, SAction<int, T>>(start, end, get, set); |
| | | 11 | | |
| | | 12 | | /// <summary>Reverses the values in an <see cref="int"/> indexed sequence.</summary> |
| | | 13 | | /// <typeparam name="T">The type of values to reverse.</typeparam> |
| | | 14 | | /// <typeparam name="TGet">The type of the get function.</typeparam> |
| | | 15 | | /// <typeparam name="TSet">The type of the set function.</typeparam> |
| | | 16 | | /// <param name="start">The starting index of the reverse.</param> |
| | | 17 | | /// <param name="end">The ending index of the reverse.</param> |
| | | 18 | | /// <param name="get">The get function.</param> |
| | | 19 | | /// <param name="set">The set function.</param> |
| | | 20 | | public static void Reverse<T, TGet, TSet>(int start, int end, TGet get = default, TSet set = default) |
| | | 21 | | where TGet : struct, IFunc<int, T> |
| | | 22 | | where TSet : struct, IAction<int, T> |
| | 24182 | 23 | | { |
| | 24182 | 24 | | if (start <= end) |
| | 24166 | 25 | | { |
| | 24166 | 26 | | int mid = start + (end - start) / 2; |
| | 12537972 | 27 | | for (int a = start, b = end; a <= mid; a++, b--) |
| | 4155158 | 28 | | { |
| | 4155158 | 29 | | Swap<T, TGet, TSet>(a, b, get, set); |
| | 4155158 | 30 | | } |
| | 24166 | 31 | | } |
| | | 32 | | else |
| | 16 | 33 | | { |
| | 16 | 34 | | int mid = start - (start - end) / 2; |
| | 162 | 35 | | for (int a = start, b = end; a >= mid; a--, b++) |
| | 38 | 36 | | { |
| | 38 | 37 | | Swap<T, TGet, TSet>(a, b, get, set); |
| | 38 | 38 | | } |
| | 16 | 39 | | } |
| | 24182 | 40 | | } |
| | | 41 | | |
| | | 42 | | #endregion |
| | | 43 | | |
| | | 44 | | #region Shuffle |
| | | 45 | | |
| | | 46 | | #pragma warning disable CS1711, CS1572 |
| | | 47 | | |
| | | 48 | | /// <summary> |
| | | 49 | | /// Sorts values into a randomized order.<br/> |
| | | 50 | | /// Runtime: O(n)<br/> |
| | | 51 | | /// Memory: O(1) |
| | | 52 | | /// </summary> |
| | | 53 | | /// <typeparam name="T">The type of values to shuffle.</typeparam> |
| | | 54 | | /// <typeparam name="TGet">The type of the get function.</typeparam> |
| | | 55 | | /// <typeparam name="TSet">The type of the set function.</typeparam> |
| | | 56 | | /// <param name="start">The starting index of the shuffle.</param> |
| | | 57 | | /// <param name="end">The ending index of the shuffle.</param> |
| | | 58 | | /// <param name="get">The get function.</param> |
| | | 59 | | /// <param name="set">The set function.</param> |
| | | 60 | | /// <param name="random">The random to shuffle with.</param> |
| | | 61 | | /// <param name="span">The span to shuffle.</param> |
| | | 62 | | [Obsolete(NotIntended, true)] |
| | 1 | 63 | | public static void XML_Shuffle() => throw new DocumentationMethodException(); |
| | | 64 | | |
| | | 65 | | #pragma warning restore CS1711, CS1572 |
| | | 66 | | |
| | | 67 | | /// <inheritdoc cref="XML_Shuffle"/> |
| | | 68 | | public static void Shuffle<T>(int start, int end, Func<int, T> get, Action<int, T> set, Random? random = null) => |
| | 0 | 69 | | Shuffle<T, SFunc<int, T>, SAction<int, T>>(start, end, get, set, random); |
| | | 70 | | |
| | | 71 | | /// <inheritdoc cref="XML_Shuffle"/> |
| | | 72 | | public static void Shuffle<T, TGet, TSet>(int start, int end, TGet get = default, TSet set = default, Random? random = |
| | | 73 | | where TGet : struct, IFunc<int, T> |
| | | 74 | | where TSet : struct, IAction<int, T> => |
| | 0 | 75 | | Shuffle<T, TGet, TSet, RandomNextIntMinValueIntMaxValue>(start, end, get, set, random ?? new Random()); |
| | | 76 | | |
| | | 77 | | /// <inheritdoc cref="XML_Shuffle"/> |
| | | 78 | | public static void Shuffle<T, TGet, TSet, TRandom>(int start, int end, TGet get = default, TSet set = default, TRandom |
| | | 79 | | where TGet : struct, IFunc<int, T> |
| | | 80 | | where TSet : struct, IAction<int, T> |
| | | 81 | | where TRandom : struct, IFunc<int, int, int> |
| | 2030 | 82 | | { |
| | 26196 | 83 | | for (int i = start; i <= end; i++) |
| | 11068 | 84 | | { |
| | 11068 | 85 | | int randomIndex = random.Invoke(start, end); |
| | 11068 | 86 | | Swap<T, TGet, TSet>(i, randomIndex, get, set); |
| | 11068 | 87 | | } |
| | 2030 | 88 | | } |
| | | 89 | | |
| | | 90 | | /// <inheritdoc cref="XML_Shuffle"/> |
| | | 91 | | public static void Shuffle<T>(Span<T> span, Random? random = null) => |
| | 2662 | 92 | | Shuffle<T, RandomNextIntMinValueIntMaxValue>(span, random ?? new Random()); |
| | | 93 | | |
| | | 94 | | /// <inheritdoc cref="XML_Shuffle"/> |
| | | 95 | | public static void Shuffle<T, TRandom>(Span<T> span, TRandom random = default) |
| | | 96 | | where TRandom : struct, IFunc<int, int, int> |
| | 7927 | 97 | | { |
| | 1797360 | 98 | | for (int i = 0; i < span.Length; i++) |
| | 890753 | 99 | | { |
| | 890753 | 100 | | int index = random.Invoke(0, span.Length); |
| | 890753 | 101 | | Swap(ref span[i], ref span[index]); |
| | 890753 | 102 | | } |
| | 7927 | 103 | | } |
| | | 104 | | |
| | | 105 | | #endregion |
| | | 106 | | |
| | | 107 | | #region XML |
| | | 108 | | |
| | | 109 | | #pragma warning disable SA1604, CS1572, CS1711 |
| | | 110 | | |
| | | 111 | | /// <typeparam name="T">The type of values to sort.</typeparam> |
| | | 112 | | /// <typeparam name="TCompare">The type of compare function.</typeparam> |
| | | 113 | | /// <typeparam name="TGet">The type of get function.</typeparam> |
| | | 114 | | /// <typeparam name="TSet">The type of set function.</typeparam> |
| | | 115 | | /// <param name="compare">The compare function.</param> |
| | | 116 | | /// <param name="get">The get function.</param> |
| | | 117 | | /// <param name="set">The set function.</param> |
| | | 118 | | /// <param name="start">The starting index of the sort.</param> |
| | | 119 | | /// <param name="end">The ending index of the sort.</param> |
| | | 120 | | /// <param name="array">The array to be sorted.</param> |
| | | 121 | | /// <param name="span">The span to be sorted.</param> |
| | | 122 | | [Obsolete(NotIntended, true)] |
| | 1 | 123 | | public static void XML_Sort() => throw new DocumentationMethodException(); |
| | | 124 | | |
| | | 125 | | #pragma warning restore SA1604, CS1572, CS1711 |
| | | 126 | | |
| | | 127 | | #endregion |
| | | 128 | | |
| | | 129 | | #region SortBubble |
| | | 130 | | |
| | | 131 | | /// <summary> |
| | | 132 | | /// Sorts values using the bubble sort algorithm.<br/> |
| | | 133 | | /// Runtime: Ω(n), ε(n^2), O(n^2)<br/> |
| | | 134 | | /// Memory: O(1)<br/> |
| | | 135 | | /// Stable: True |
| | | 136 | | /// </summary> |
| | | 137 | | /// <inheritdoc cref="XML_Sort"/> |
| | | 138 | | [Obsolete(NotIntended, true)] |
| | 1 | 139 | | public static void XML_SortBubble() => throw new DocumentationMethodException(); |
| | | 140 | | |
| | | 141 | | /// <inheritdoc cref="XML_SortBubble"/> |
| | | 142 | | public static void SortBubble<T>(int start, int end, Func<int, T> get, Action<int, T> set, Func<T, T, CompareResult>? |
| | 83 | 143 | | SortBubble<T, SFunc<int, T>, SAction<int, T>, SFunc<T, T, CompareResult>>(start, end, get, set, compare ?? Compare); |
| | | 144 | | |
| | | 145 | | /// <inheritdoc cref="XML_SortBubble"/> |
| | | 146 | | public static void SortBubble<T, TGet, TSet, TCompare>(int start, int end, TGet get = default, TSet set = default, TCo |
| | | 147 | | where TCompare : struct, IFunc<T, T, CompareResult> |
| | | 148 | | where TGet : struct, IFunc<int, T> |
| | | 149 | | where TSet : struct, IAction<int, T> |
| | 83 | 150 | | { |
| | 24828 | 151 | | for (int i = start; i <= end; i++) |
| | 12331 | 152 | | { |
| | 22151902 | 153 | | for (int j = start; j <= end - 1; j++) |
| | 11063620 | 154 | | { |
| | 11063620 | 155 | | if (compare.Invoke(get.Invoke(j), get.Invoke(j + 1)) is Greater) |
| | 2786905 | 156 | | { |
| | 2786905 | 157 | | Swap<T, TGet, TSet>(j + 1, j, get, set); |
| | 2786905 | 158 | | } |
| | 11063620 | 159 | | } |
| | 12331 | 160 | | } |
| | 83 | 161 | | } |
| | | 162 | | |
| | | 163 | | /// <inheritdoc cref="XML_SortBubble"/> |
| | | 164 | | public static void SortBubble<T>(Span<T> span, Func<T, T, CompareResult>? compare = null) => |
| | 83 | 165 | | SortBubble<T, SFunc<T, T, CompareResult>>(span, compare ?? Compare); |
| | | 166 | | |
| | | 167 | | /// <inheritdoc cref="XML_SortBubble"/> |
| | | 168 | | public static void SortBubble<T, TCompare>(Span<T> span, TCompare compare = default) |
| | | 169 | | where TCompare : struct, IFunc<T, T, CompareResult> |
| | 83 | 170 | | { |
| | 24828 | 171 | | for (int i = 0; i <= span.Length - 1; i++) |
| | 12331 | 172 | | { |
| | 22151902 | 173 | | for (int j = 0; j <= span.Length - 2; j++) |
| | 11063620 | 174 | | { |
| | 11063620 | 175 | | if (compare.Invoke(span[j], span[j + 1]) is Greater) |
| | 2786905 | 176 | | { |
| | 2786905 | 177 | | Swap(ref span[j], ref span[j + 1]); |
| | 2786905 | 178 | | } |
| | 11063620 | 179 | | } |
| | 12331 | 180 | | } |
| | 83 | 181 | | } |
| | | 182 | | |
| | | 183 | | #endregion |
| | | 184 | | |
| | | 185 | | #region SortSelection |
| | | 186 | | |
| | | 187 | | /// <summary> |
| | | 188 | | /// Sorts values using the selection sort algoritm.<br/> |
| | | 189 | | /// Runtime: Ω(n^2), ε(n^2), O(n^2)<br/> |
| | | 190 | | /// Memory: O(1)<br/> |
| | | 191 | | /// Stable: False |
| | | 192 | | /// </summary> |
| | | 193 | | /// <inheritdoc cref="XML_Sort"/> |
| | | 194 | | [Obsolete(NotIntended, true)] |
| | 1 | 195 | | public static void XML_SortSelection() => throw new DocumentationMethodException(); |
| | | 196 | | |
| | | 197 | | /// <inheritdoc cref="XML_SortSelection"/> |
| | | 198 | | public static void SortSelection<T>(int start, int end, Func<int, T> get, Action<int, T> set, Func<T, T, CompareResult |
| | 83 | 199 | | SortSelection<T, SFunc<int, T>, SAction<int, T>, SFunc<T, T, CompareResult>>(start, end, get, set, compare ?? Compar |
| | | 200 | | |
| | | 201 | | /// <inheritdoc cref="XML_SortSelection"/> |
| | | 202 | | public static void SortSelection<T, TGet, TSet, TCompare>(int start, int end, TGet get = default, TSet set = default, |
| | | 203 | | where TCompare : struct, IFunc<T, T, CompareResult> |
| | | 204 | | where TGet : struct, IFunc<int, T> |
| | | 205 | | where TSet : struct, IAction<int, T> |
| | 83 | 206 | | { |
| | 24828 | 207 | | for (int i = start; i <= end; i++) |
| | 12331 | 208 | | { |
| | 12331 | 209 | | int min = i; |
| | 11088282 | 210 | | for (int j = i + 1; j <= end; j++) |
| | 5531810 | 211 | | { |
| | 5531810 | 212 | | if (compare.Invoke(get.Invoke(j), get.Invoke(min)) is Less) |
| | 63822 | 213 | | { |
| | 63822 | 214 | | min = j; |
| | 63822 | 215 | | } |
| | 5531810 | 216 | | } |
| | 12331 | 217 | | Swap<T, TGet, TSet>(min, i, get, set); |
| | 12331 | 218 | | } |
| | 83 | 219 | | } |
| | | 220 | | |
| | | 221 | | /// <inheritdoc cref="XML_SortSelection"/> |
| | | 222 | | public static void SortSelection<T>(Span<T> span, Func<T, T, CompareResult>? compare = null) => |
| | 83 | 223 | | SortSelection<T, SFunc<T, T, CompareResult>>(span, compare ?? Compare); |
| | | 224 | | |
| | | 225 | | /// <inheritdoc cref="XML_SortSelection"/> |
| | | 226 | | public static void SortSelection<T, TCompare>(Span<T> span, TCompare compare = default) |
| | | 227 | | where TCompare : struct, IFunc<T, T, CompareResult> |
| | 83 | 228 | | { |
| | 24828 | 229 | | for (int i = 0; i < span.Length; i++) |
| | 12331 | 230 | | { |
| | 12331 | 231 | | int min = i; |
| | 11088282 | 232 | | for (int j = i + 1; j < span.Length; j++) |
| | 5531810 | 233 | | { |
| | 5531810 | 234 | | if (compare.Invoke(span[j], span[min]) is Less) |
| | 63822 | 235 | | { |
| | 63822 | 236 | | min = j; |
| | 63822 | 237 | | } |
| | 5531810 | 238 | | } |
| | 12331 | 239 | | Swap(ref span[min], ref span[i]); |
| | 12331 | 240 | | } |
| | 83 | 241 | | } |
| | | 242 | | |
| | | 243 | | #endregion |
| | | 244 | | |
| | | 245 | | #region SortInsertion |
| | | 246 | | |
| | | 247 | | /// <summary> |
| | | 248 | | /// Sorts values using the insertion sort algorithm.<br/> |
| | | 249 | | /// Runtime: Ω(n), ε(n^2), O(n^2)<br/> |
| | | 250 | | /// Memory: O(1)<br/> |
| | | 251 | | /// Stable: True |
| | | 252 | | /// </summary> |
| | | 253 | | /// <inheritdoc cref="XML_Sort"/> |
| | | 254 | | [Obsolete(NotIntended, true)] |
| | 1 | 255 | | public static void XML_SortInsertion() => throw new DocumentationMethodException(); |
| | | 256 | | |
| | | 257 | | /// <inheritdoc cref="XML_SortInsertion"/> |
| | | 258 | | public static void SortInsertion<T>(int start, int end, Func<int, T> get, Action<int, T> set, Func<T, T, CompareResult |
| | 83 | 259 | | SortInsertion<T, SFunc<int, T>, SAction<int, T>, SFunc<T, T, CompareResult>>(start, end, get, set, compare ?? Compar |
| | | 260 | | |
| | | 261 | | /// <inheritdoc cref="XML_SortInsertion"/> |
| | | 262 | | public static void SortInsertion<T, TGet, TSet, TCompare>(int start, int end, TGet get = default, TSet set = default, |
| | | 263 | | where TCompare : struct, IFunc<T, T, CompareResult> |
| | | 264 | | where TGet : struct, IFunc<int, T> |
| | | 265 | | where TSet : struct, IAction<int, T> |
| | 1596 | 266 | | { |
| | 72046 | 267 | | for (int i = start + 1; i <= end; i++) |
| | 34427 | 268 | | { |
| | 34427 | 269 | | T temp = get.Invoke(i); |
| | 34427 | 270 | | int j = i; |
| | 5873387 | 271 | | for (; j > start && compare.Invoke(get.Invoke(j - 1), temp) is Greater; j--) |
| | 2919480 | 272 | | { |
| | 2919480 | 273 | | set.Invoke(j, get.Invoke(j - 1)); |
| | 2919480 | 274 | | } |
| | 34427 | 275 | | set.Invoke(j, temp); |
| | 34427 | 276 | | } |
| | 1596 | 277 | | } |
| | | 278 | | |
| | | 279 | | /// <inheritdoc cref="XML_SortInsertion"/> |
| | | 280 | | public static void SortInsertion<T>(Span<T> span, Func<T, T, CompareResult>? compare = null) => |
| | 83 | 281 | | SortInsertion<T, SFunc<T, T, CompareResult>>(span, compare ?? Compare); |
| | | 282 | | |
| | | 283 | | /// <inheritdoc cref="XML_SortInsertion"/> |
| | | 284 | | public static void SortInsertion<T, TCompare>(Span<T> span, TCompare compare = default) |
| | | 285 | | where TCompare : struct, IFunc<T, T, CompareResult> |
| | 1596 | 286 | | { |
| | 71306 | 287 | | for (int i = 1; i <= span.Length - 1; i++) |
| | 34057 | 288 | | { |
| | 34057 | 289 | | T temp = span[i]; |
| | | 290 | | int j; |
| | 5885644 | 291 | | for (j = i; j > 0 && compare.Invoke(span[j - 1], temp) is Greater; j--) |
| | 2908765 | 292 | | { |
| | 2908765 | 293 | | span[j] = span[j - 1]; |
| | 2908765 | 294 | | } |
| | 34057 | 295 | | span[j] = temp; |
| | 34057 | 296 | | } |
| | 1596 | 297 | | } |
| | | 298 | | |
| | | 299 | | #endregion |
| | | 300 | | |
| | | 301 | | #region SortQuick |
| | | 302 | | |
| | | 303 | | /// <summary> |
| | | 304 | | /// Sorts values using the quick sort algorithm.<br/> |
| | | 305 | | /// Runtime: Ω(n*ln(n)), ε(n*ln(n)), O(n^2)<br/> |
| | | 306 | | /// Memory: ln(n)<br/> |
| | | 307 | | /// Stable: False |
| | | 308 | | /// </summary> |
| | | 309 | | /// <inheritdoc cref="XML_Sort"/> |
| | | 310 | | [Obsolete(NotIntended, true)] |
| | 1 | 311 | | public static void XML_SortQuick() => throw new DocumentationMethodException(); |
| | | 312 | | |
| | | 313 | | /// <inheritdoc cref="XML_SortQuick"/> |
| | | 314 | | public static void SortQuick<T>(int start, int end, Func<int, T> get, Action<int, T> set, Func<T, T, CompareResult>? c |
| | 83 | 315 | | SortQuick<T, SFunc<int, T>, SAction<int, T>, SFunc<T, T, CompareResult>>(start, end, get, set, compare ?? Compare); |
| | | 316 | | |
| | | 317 | | /// <inheritdoc cref="XML_SortQuick"/> |
| | | 318 | | public static void SortQuick<T, TGet, TSet, TCompare>(int start, int end, TGet get = default, TSet set = default, TCom |
| | | 319 | | where TCompare : struct, IFunc<T, T, CompareResult> |
| | | 320 | | where TGet : struct, IFunc<int, T> |
| | | 321 | | where TSet : struct, IAction<int, T> |
| | 83 | 322 | | { |
| | 83 | 323 | | SortQuick_Recursive(start, end - start + 1); |
| | | 324 | | |
| | | 325 | | void SortQuick_Recursive(int start, int length) |
| | 16387 | 326 | | { |
| | 16387 | 327 | | if (length > 1) |
| | 8152 | 328 | | { |
| | 8152 | 329 | | T pivot = get.Invoke(start); |
| | 8152 | 330 | | int i = start; |
| | 8152 | 331 | | int j = start + length - 1; |
| | 8152 | 332 | | int k = j; |
| | 139363 | 333 | | while (i <= j) |
| | 131211 | 334 | | { |
| | 131211 | 335 | | if (compare.Invoke(get.Invoke(j), pivot) is Less) |
| | 65692 | 336 | | { |
| | 65692 | 337 | | Swap<T, TGet, TSet>(i++, j, get, set); |
| | 65692 | 338 | | } |
| | 65519 | 339 | | else if (compare.Invoke(get.Invoke(j), pivot) is Equal) |
| | 8188 | 340 | | { |
| | 8188 | 341 | | j--; |
| | 8188 | 342 | | } |
| | | 343 | | else |
| | 57331 | 344 | | { |
| | 57331 | 345 | | Swap<T, TGet, TSet>(k--, j--, get, set); |
| | 57331 | 346 | | } |
| | 131211 | 347 | | } |
| | 8152 | 348 | | SortQuick_Recursive(start, i - start); |
| | 8152 | 349 | | SortQuick_Recursive(k + 1, start + length - (k + 1)); |
| | 8152 | 350 | | } |
| | 16387 | 351 | | } |
| | 83 | 352 | | } |
| | | 353 | | |
| | | 354 | | /// <inheritdoc cref="XML_SortQuick"/> |
| | | 355 | | public static void SortQuick<T>(Span<T> span, Func<T, T, CompareResult>? compare = null) => |
| | 105 | 356 | | SortQuick<T, SFunc<T, T, CompareResult>>(span, compare ?? Compare); |
| | | 357 | | |
| | | 358 | | /// <inheritdoc cref="XML_SortQuick"/> |
| | | 359 | | public static void SortQuick<T, TCompare>(Span<T> span, TCompare compare = default) |
| | | 360 | | where TCompare : struct, IFunc<T, T, CompareResult> |
| | 105 | 361 | | { |
| | 105 | 362 | | SortQuick_Recursive(span, 0, span.Length); |
| | | 363 | | |
| | | 364 | | void SortQuick_Recursive(Span<T> span, int startIndex, int len) |
| | 16453 | 365 | | { |
| | 16453 | 366 | | if (len > 1) |
| | 8174 | 367 | | { |
| | 8174 | 368 | | T pivot = span[startIndex]; |
| | 8174 | 369 | | int i = startIndex; |
| | 8174 | 370 | | int j = startIndex + len - 1; |
| | 8174 | 371 | | int k = j; |
| | 139429 | 372 | | while (i <= j) |
| | 131255 | 373 | | { |
| | 131255 | 374 | | if (compare.Invoke(span[j], pivot) is Less) |
| | 65699 | 375 | | { |
| | 65699 | 376 | | Swap(ref span[i++], ref span[j]); |
| | 65699 | 377 | | } |
| | 65556 | 378 | | else if (compare.Invoke(span[j], pivot) is Equal) |
| | 8220 | 379 | | { |
| | 8220 | 380 | | j--; |
| | 8220 | 381 | | } |
| | | 382 | | else |
| | 57336 | 383 | | { |
| | 57336 | 384 | | Swap(ref span[k--], ref span[j--]); |
| | 57336 | 385 | | } |
| | 131255 | 386 | | } |
| | 8174 | 387 | | SortQuick_Recursive(span, startIndex, i - startIndex); |
| | 8174 | 388 | | SortQuick_Recursive(span, k + 1, startIndex + len - (k + 1)); |
| | 8174 | 389 | | } |
| | 16453 | 390 | | } |
| | 105 | 391 | | } |
| | | 392 | | |
| | | 393 | | #endregion |
| | | 394 | | |
| | | 395 | | #region SortMerge |
| | | 396 | | |
| | | 397 | | /// <summary> |
| | | 398 | | /// Sorts values using the merge sort algorithm.<br/> |
| | | 399 | | /// Runtime: Ω(n*ln(n)), ε(n*ln(n)), O(n*ln(n))<br/> |
| | | 400 | | /// Memory: Θ(n)<br/> |
| | | 401 | | /// Stable: True |
| | | 402 | | /// </summary> |
| | | 403 | | /// <inheritdoc cref="XML_Sort"/> |
| | | 404 | | [Obsolete(NotIntended, true)] |
| | 1 | 405 | | public static void XML_SortMerge() => throw new DocumentationMethodException(); |
| | | 406 | | |
| | | 407 | | /// <inheritdoc cref="XML_SortMerge"/> |
| | | 408 | | public static void SortMerge<T>(int start, int end, Func<int, T> get, Action<int, T> set, Func<T, T, CompareResult>? c |
| | 83 | 409 | | SortMerge<T, SFunc<int, T>, SAction<int, T>, SFunc<T, T, CompareResult>>(start, end, get, set, compare ?? Compare); |
| | | 410 | | |
| | | 411 | | /// <inheritdoc cref="XML_SortMerge"/> |
| | | 412 | | public static void SortMerge<T, TGet, TSet, TCompare>(int start, int end, TGet get = default, TSet set = default, TCom |
| | | 413 | | where TCompare : struct, IFunc<T, T, CompareResult> |
| | | 414 | | where TGet : struct, IFunc<int, T> |
| | | 415 | | where TSet : struct, IAction<int, T> |
| | 83 | 416 | | { |
| | 83 | 417 | | SortMerge_Recursive(start, end - start + 1); |
| | | 418 | | |
| | | 419 | | void SortMerge_Recursive(int start, int length) |
| | 24589 | 420 | | { |
| | 24589 | 421 | | if (length > 1) |
| | 12253 | 422 | | { |
| | 12253 | 423 | | int half = length / 2; |
| | 12253 | 424 | | SortMerge_Recursive(start, half); |
| | 12253 | 425 | | SortMerge_Recursive(start + half, length - half); |
| | 12253 | 426 | | Span<T> sorted = new T[length]; |
| | 12253 | 427 | | int i = start; |
| | 12253 | 428 | | int j = start + half; |
| | 12253 | 429 | | int k = 0; |
| | 114147 | 430 | | while (i < start + half && j < start + length) |
| | 101894 | 431 | | { |
| | 101894 | 432 | | if (compare.Invoke(get.Invoke(i), get.Invoke(j)) is Greater) |
| | 51777 | 433 | | { |
| | 51777 | 434 | | sorted[k++] = get.Invoke(j++); |
| | 51777 | 435 | | } |
| | | 436 | | else |
| | 50117 | 437 | | { |
| | 50117 | 438 | | sorted[k++] = get.Invoke(i++); |
| | 50117 | 439 | | } |
| | 101894 | 440 | | } |
| | 39788 | 441 | | for (int h = 0; h < start + half - i; h++) |
| | 7641 | 442 | | { |
| | 7641 | 443 | | sorted[k + h] = get.Invoke(i + h); |
| | 7641 | 444 | | } |
| | 40058 | 445 | | for (int h = 0; h < start + length - j; h++) |
| | 7776 | 446 | | { |
| | 7776 | 447 | | sorted[k + h] = get.Invoke(j + h); |
| | 7776 | 448 | | } |
| | 259128 | 449 | | for (int h = 0; h < length; h++) |
| | 117311 | 450 | | { |
| | 117311 | 451 | | set.Invoke(start + h, sorted[0 + h]); |
| | 117311 | 452 | | } |
| | 12253 | 453 | | } |
| | 24589 | 454 | | } |
| | 83 | 455 | | } |
| | | 456 | | |
| | | 457 | | /// <inheritdoc cref="XML_SortMerge"/> |
| | | 458 | | public static void SortMerge<T>(Span<T> span, Func<T, T, CompareResult>? compare = null) => |
| | 98 | 459 | | SortMerge<T, SFunc<T, T, CompareResult>>(span, compare ?? Compare); |
| | | 460 | | |
| | | 461 | | /// <inheritdoc cref="XML_SortMerge"/> |
| | | 462 | | public static void SortMerge<T, TCompare>(Span<T> span, TCompare compare = default) |
| | | 463 | | where TCompare : struct, IFunc<T, T, CompareResult> |
| | 98 | 464 | | { |
| | 98 | 465 | | SortMerge_Recursive(span); |
| | | 466 | | |
| | | 467 | | void SortMerge_Recursive(Span<T> span) |
| | 24730 | 468 | | { |
| | 24730 | 469 | | if (span.Length > 1) |
| | 12316 | 470 | | { |
| | 12316 | 471 | | int half = span.Length / 2; |
| | 12316 | 472 | | SortMerge_Recursive(span[..half]); |
| | 12316 | 473 | | SortMerge_Recursive(span[half..]); |
| | 12316 | 474 | | T[] sorted = new T[span.Length]; |
| | 12316 | 475 | | int i = 0; |
| | 12316 | 476 | | int j = half; |
| | 12316 | 477 | | int k = 0; |
| | 114299 | 478 | | while (i < half && j < span.Length) |
| | 101983 | 479 | | { |
| | 101983 | 480 | | if (compare.Invoke(span[i], span[j]) is Greater) |
| | 51793 | 481 | | { |
| | 51793 | 482 | | sorted[k++] = span[j++]; |
| | 51793 | 483 | | } |
| | | 484 | | else |
| | 50190 | 485 | | { |
| | 50190 | 486 | | sorted[k++] = span[i++]; |
| | 50190 | 487 | | } |
| | 101983 | 488 | | } |
| | 39930 | 489 | | for (int h = 0; h < half - i; h++) |
| | 7649 | 490 | | { |
| | 7649 | 491 | | sorted[k + h] = span[i + h]; |
| | 7649 | 492 | | } |
| | 40374 | 493 | | for (int h = 0; h < span.Length - j; h++) |
| | 7871 | 494 | | { |
| | 7871 | 495 | | sorted[k + h] = span[j + h]; |
| | 7871 | 496 | | } |
| | 259638 | 497 | | for (int h = 0; h < span.Length; h++) |
| | 117503 | 498 | | { |
| | 117503 | 499 | | span[h] = sorted[0 + h]; |
| | 117503 | 500 | | } |
| | 12316 | 501 | | } |
| | 24730 | 502 | | } |
| | 98 | 503 | | } |
| | | 504 | | |
| | | 505 | | #endregion |
| | | 506 | | |
| | | 507 | | #region SortHeap |
| | | 508 | | |
| | | 509 | | /// <summary> |
| | | 510 | | /// Sorts values using the heap sort algorithm.<br/> |
| | | 511 | | /// Runtime: Ω(n*ln(n)), ε(n*ln(n)), O(n^2)<br/> |
| | | 512 | | /// Memory: O(1)<br/> |
| | | 513 | | /// Stable: False |
| | | 514 | | /// </summary> |
| | | 515 | | /// <inheritdoc cref="XML_Sort"/> |
| | | 516 | | [Obsolete(NotIntended, true)] |
| | 1 | 517 | | public static void XML_SortHeap() => throw new DocumentationMethodException(); |
| | | 518 | | |
| | | 519 | | /// <inheritdoc cref="XML_SortHeap"/> |
| | | 520 | | public static void SortHeap<T>(int start, int end, Func<int, T> get, Action<int, T> set, Func<T, T, CompareResult>? co |
| | 83 | 521 | | SortHeap<T, SFunc<int, T>, SAction<int, T>, SFunc<T, T, CompareResult>>(start, end, get, set, compare ?? Compare); |
| | | 522 | | |
| | | 523 | | /// <inheritdoc cref="XML_SortHeap"/> |
| | | 524 | | public static void SortHeap<T, TGet, TSet, TCompare>(int start, int end, TGet get = default, TSet set = default, TComp |
| | | 525 | | where TCompare : struct, IFunc<T, T, CompareResult> |
| | | 526 | | where TGet : struct, IFunc<int, T> |
| | | 527 | | where TSet : struct, IAction<int, T> |
| | 83 | 528 | | { |
| | 83 | 529 | | int heapSize = end - start + 1; |
| | 12620 | 530 | | for (int i = heapSize / 2; i >= 0; i--) |
| | 6227 | 531 | | { |
| | 6227 | 532 | | MaxSortHeapify(heapSize + start, i, start); |
| | 6227 | 533 | | } |
| | 24828 | 534 | | for (int i = end; i >= start; i--) |
| | 12331 | 535 | | { |
| | 12331 | 536 | | Swap<T, TGet, TSet>(start, i, get, set); |
| | 12331 | 537 | | heapSize--; |
| | 12331 | 538 | | MaxSortHeapify(heapSize + start, 0, start); |
| | 12331 | 539 | | } |
| | | 540 | | void MaxSortHeapify(int heapSize, int index, int offset) |
| | 112437 | 541 | | { |
| | 112437 | 542 | | int left = ((index + 1) * 2 - 1) + offset; |
| | 112437 | 543 | | int right = ((index + 1) * 2) + offset; |
| | 112437 | 544 | | index += offset; |
| | 112437 | 545 | | int largest = index; |
| | 112437 | 546 | | if (left < heapSize && compare.Invoke(get.Invoke(left), get.Invoke(largest)) is Greater) |
| | 90360 | 547 | | { |
| | 90360 | 548 | | largest = left; |
| | 90360 | 549 | | } |
| | 112437 | 550 | | if (right < heapSize && compare.Invoke(get.Invoke(right), get.Invoke(largest)) is Greater) |
| | 44994 | 551 | | { |
| | 44994 | 552 | | largest = right; |
| | 44994 | 553 | | } |
| | 112437 | 554 | | if (largest != index) |
| | 93879 | 555 | | { |
| | 93879 | 556 | | Swap<T, TGet, TSet>(index, largest, get, set); |
| | 93879 | 557 | | MaxSortHeapify(heapSize, largest - offset, offset); |
| | 93879 | 558 | | } |
| | 112437 | 559 | | } |
| | 83 | 560 | | } |
| | | 561 | | |
| | | 562 | | /// <inheritdoc cref="XML_SortHeap"/> |
| | | 563 | | public static void SortHeap<T>(Span<T> span, Func<T, T, CompareResult>? compare = null) => |
| | 83 | 564 | | SortHeap<T, SFunc<T, T, CompareResult>>(span, compare ?? Compare); |
| | | 565 | | |
| | | 566 | | /// <inheritdoc cref="XML_SortHeap"/> |
| | | 567 | | public static void SortHeap<T, TCompare>(Span<T> span, TCompare compare = default) |
| | | 568 | | where TCompare : struct, IFunc<T, T, CompareResult> |
| | 83 | 569 | | { |
| | 83 | 570 | | int start = 0; |
| | 83 | 571 | | int end = span.Length - 1; |
| | 83 | 572 | | int heapSize = end - start + 1; |
| | 12620 | 573 | | for (int i = heapSize / 2; i >= 0; i--) |
| | 6227 | 574 | | { |
| | 6227 | 575 | | MaxSortHeapify(span, heapSize + start, i, start); |
| | 6227 | 576 | | } |
| | 24828 | 577 | | for (int i = end; i >= start; i--) |
| | 12331 | 578 | | { |
| | 12331 | 579 | | Swap(ref span[start], ref span[i]); |
| | 12331 | 580 | | heapSize--; |
| | 12331 | 581 | | MaxSortHeapify(span, heapSize + start, 0, start); |
| | 12331 | 582 | | } |
| | | 583 | | void MaxSortHeapify(Span<T> span, int heapSize, int index, int offset) |
| | 112437 | 584 | | { |
| | 112437 | 585 | | int left = ((index + 1) * 2 - 1) + offset; |
| | 112437 | 586 | | int right = ((index + 1) * 2) + offset; |
| | 112437 | 587 | | index += offset; |
| | 112437 | 588 | | int largest = index; |
| | 112437 | 589 | | if (left < heapSize && compare.Invoke(span[left], span[largest]) is Greater) |
| | 90360 | 590 | | { |
| | 90360 | 591 | | largest = left; |
| | 90360 | 592 | | } |
| | 112437 | 593 | | if (right < heapSize && compare.Invoke(span[right], span[largest]) is Greater) |
| | 44994 | 594 | | { |
| | 44994 | 595 | | largest = right; |
| | 44994 | 596 | | } |
| | 112437 | 597 | | if (largest != index) |
| | 93879 | 598 | | { |
| | 93879 | 599 | | Swap(ref span[index], ref span[largest]); |
| | 93879 | 600 | | MaxSortHeapify(span, heapSize, largest - offset, offset); |
| | 93879 | 601 | | } |
| | 112437 | 602 | | } |
| | 83 | 603 | | } |
| | | 604 | | |
| | | 605 | | #endregion |
| | | 606 | | |
| | | 607 | | #region SortOddEven |
| | | 608 | | |
| | | 609 | | /// <summary> |
| | | 610 | | /// Sorts values using the odd even sort algorithm.<br/> |
| | | 611 | | /// Runtime: Ω(n), ε(n^2), O(n^2)<br/> |
| | | 612 | | /// Memory: O(1)<br/> |
| | | 613 | | /// Stable: True |
| | | 614 | | /// </summary> |
| | | 615 | | /// <inheritdoc cref="XML_Sort"/> |
| | | 616 | | [Obsolete(NotIntended, true)] |
| | 1 | 617 | | public static void XML_SortOddEven() => throw new DocumentationMethodException(); |
| | | 618 | | |
| | | 619 | | /// <inheritdoc cref="XML_SortOddEven"/> |
| | | 620 | | public static void SortOddEven<T>(int start, int end, Func<int, T> get, Action<int, T> set, Func<T, T, CompareResult>? |
| | 83 | 621 | | SortOddEven<T, SFunc<int, T>, SAction<int, T>, SFunc<T, T, CompareResult>>(start, end, get, set, compare ?? Compare) |
| | | 622 | | |
| | | 623 | | /// <inheritdoc cref="XML_SortOddEven"/> |
| | | 624 | | public static void SortOddEven<T, TGet, TSet, TCompare>(int start, int end, TGet get = default, TSet set = default, TC |
| | | 625 | | where TCompare : struct, IFunc<T, T, CompareResult> |
| | | 626 | | where TGet : struct, IFunc<int, T> |
| | | 627 | | where TSet : struct, IAction<int, T> |
| | 83 | 628 | | { |
| | 83 | 629 | | bool sorted = false; |
| | 6115 | 630 | | while (!sorted) |
| | 6032 | 631 | | { |
| | 6032 | 632 | | sorted = true; |
| | 5387232 | 633 | | for (int i = start; i < end; i += 2) |
| | 2687584 | 634 | | { |
| | 2687584 | 635 | | if (compare.Invoke(get.Invoke(i), get.Invoke(i + 1)) is Greater) |
| | 1393774 | 636 | | { |
| | 1393774 | 637 | | Swap<T, TGet, TSet>(i, i + 1, get, set); |
| | 1393774 | 638 | | sorted = false; |
| | 1393774 | 639 | | } |
| | 2687584 | 640 | | } |
| | 5381704 | 641 | | for (int i = start + 1; i < end; i += 2) |
| | 2684820 | 642 | | { |
| | 2684820 | 643 | | if (compare.Invoke(get.Invoke(i), get.Invoke(i + 1)) is Greater) |
| | 1393131 | 644 | | { |
| | 1393131 | 645 | | Swap<T, TGet, TSet>(i, i + 1, get, set); |
| | 1393131 | 646 | | sorted = false; |
| | 1393131 | 647 | | } |
| | 2684820 | 648 | | } |
| | 6032 | 649 | | } |
| | 83 | 650 | | } |
| | | 651 | | |
| | | 652 | | /// <inheritdoc cref="XML_SortOddEven"/> |
| | | 653 | | public static void SortOddEven<T>(Span<T> span, Func<T, T, CompareResult>? compare = null) => |
| | 83 | 654 | | SortOddEven<T, SFunc<T, T, CompareResult>>(span, compare ?? Compare); |
| | | 655 | | |
| | | 656 | | /// <inheritdoc cref="XML_SortOddEven"/> |
| | | 657 | | public static void SortOddEven<T, TCompare>(Span<T> span, TCompare compare = default) |
| | | 658 | | where TCompare : struct, IFunc<T, T, CompareResult> |
| | 83 | 659 | | { |
| | 83 | 660 | | bool sorted = false; |
| | 6115 | 661 | | while (!sorted) |
| | 6032 | 662 | | { |
| | 6032 | 663 | | sorted = true; |
| | 5387232 | 664 | | for (int i = 0; i < span.Length - 1; i += 2) |
| | 2687584 | 665 | | { |
| | 2687584 | 666 | | if (compare.Invoke(span[i], span[i + 1]) is Greater) |
| | 1393774 | 667 | | { |
| | 1393774 | 668 | | Swap(ref span[i], ref span[i + 1]); |
| | 1393774 | 669 | | sorted = false; |
| | 1393774 | 670 | | } |
| | 2687584 | 671 | | } |
| | 5381704 | 672 | | for (int i = 1; i < span.Length - 1; i += 2) |
| | 2684820 | 673 | | { |
| | 2684820 | 674 | | if (compare.Invoke(span[i], span[i + 1]) is Greater) |
| | 1393131 | 675 | | { |
| | 1393131 | 676 | | Swap(ref span[i], ref span[i + 1]); |
| | 1393131 | 677 | | sorted = false; |
| | 1393131 | 678 | | } |
| | 2684820 | 679 | | } |
| | 6032 | 680 | | } |
| | 83 | 681 | | } |
| | | 682 | | |
| | | 683 | | #endregion |
| | | 684 | | |
| | | 685 | | #region SortBogo |
| | | 686 | | |
| | | 687 | | /// <summary> |
| | | 688 | | /// Sorts values using the bogo sort algorithm.<br/> |
| | | 689 | | /// Runtime: Ω(n), ε(n*n!), O(∞)<br/> |
| | | 690 | | /// Memory: O(1)<br/> |
| | | 691 | | /// Stable: False |
| | | 692 | | /// </summary> |
| | | 693 | | /// <inheritdoc cref="XML_Sort"/> |
| | | 694 | | [Obsolete(NotIntended, true)] |
| | 1 | 695 | | public static void XML_SortBogo() => throw new DocumentationMethodException(); |
| | | 696 | | |
| | | 697 | | /// <inheritdoc cref="XML_SortBogo"/> |
| | | 698 | | public static void SortBogo<T>(int start, int end, Func<int, T> get, Action<int, T> set, Func<T, T, CompareResult>? co |
| | 37 | 699 | | SortBogo<T, SFunc<int, T>, SAction<int, T>, SFunc<T, T, CompareResult>>(start, end, get, set, compare ?? Compare, ra |
| | | 700 | | |
| | | 701 | | /// <inheritdoc cref="XML_SortBogo"/> |
| | | 702 | | public static void SortBogo<T, TGet, TSet, TCompare>(int start, int end, TGet get = default, TSet set = default, TComp |
| | | 703 | | where TCompare : struct, IFunc<T, T, CompareResult> |
| | | 704 | | where TGet : struct, IFunc<int, T> |
| | | 705 | | where TSet : struct, IAction<int, T> => |
| | 37 | 706 | | SortBogo<T, TGet, TSet, TCompare, RandomNextIntMinValueIntMaxValue>(start, end, get, set, compare, random ?? new Ran |
| | | 707 | | |
| | | 708 | | /// <inheritdoc cref="XML_SortBogo"/> |
| | | 709 | | public static void SortBogo<T, TGet, TSet, TCompare, TRandom>(int start, int end, TGet get = default, TSet set = defau |
| | | 710 | | where TCompare : struct, IFunc<T, T, CompareResult> |
| | | 711 | | where TGet : struct, IFunc<int, T> |
| | | 712 | | where TSet : struct, IAction<int, T> |
| | | 713 | | where TRandom : struct, IFunc<int, int, int> |
| | 37 | 714 | | { |
| | 2067 | 715 | | while (!IsOrdered<T, TCompare, TGet>(start, end, compare, get)) |
| | 2030 | 716 | | { |
| | 2030 | 717 | | Shuffle<T, TGet, TSet, TRandom>(start, end, get, set, random); |
| | 2030 | 718 | | } |
| | 37 | 719 | | } |
| | | 720 | | |
| | | 721 | | /// <inheritdoc cref="XML_SortBogo"/> |
| | | 722 | | public static void SortBogo<T>(Span<T> span, Func<T, T, CompareResult>? compare = null, Random? random = null) => |
| | 37 | 723 | | SortBogo<T, SFunc<T, T, CompareResult>>(span, compare ?? Compare, random ?? new Random()); |
| | | 724 | | |
| | | 725 | | /// <inheritdoc cref="XML_SortBogo"/> |
| | | 726 | | public static void SortBogo<T, TCompare>(Span<T> span, TCompare compare = default, Random? random = null) |
| | | 727 | | where TCompare : struct, IFunc<T, T, CompareResult> => |
| | 37 | 728 | | SortBogo<T, TCompare, RandomNextIntMinValueIntMaxValue>(span, compare, random ?? new Random()); |
| | | 729 | | |
| | | 730 | | /// <inheritdoc cref="XML_SortBogo"/> |
| | | 731 | | public static void SortBogo<T, TCompare, TRandom>(Span<T> span, TCompare compare = default, TRandom random = default) |
| | | 732 | | where TCompare : struct, IFunc<T, T, CompareResult> |
| | | 733 | | where TRandom : struct, IFunc<int, int, int> |
| | 37 | 734 | | { |
| | 5302 | 735 | | while (!IsOrdered<T, TCompare>(span, compare)) |
| | 5265 | 736 | | { |
| | 5265 | 737 | | Shuffle(span, random); |
| | 5265 | 738 | | } |
| | 37 | 739 | | } |
| | | 740 | | |
| | | 741 | | #endregion |
| | | 742 | | |
| | | 743 | | #region SortSlow |
| | | 744 | | |
| | | 745 | | /// <summary>Sorts values using the slow sort algorithm.</summary> |
| | | 746 | | /// <inheritdoc cref="XML_Sort"/> |
| | | 747 | | [Obsolete(NotIntended, true)] |
| | 1 | 748 | | public static void XML_SortSlow() => throw new DocumentationMethodException(); |
| | | 749 | | |
| | | 750 | | /// <inheritdoc cref="XML_SortSlow"/> |
| | | 751 | | public static void SortSlow<T>(int start, int end, Func<int, T> get, Action<int, T> set, Func<T, T, CompareResult>? co |
| | 62 | 752 | | SortSlow<T, SFunc<int, T>, SAction<int, T>, SFunc<T, T, CompareResult>>(start, end, get, set, compare ?? Compare); |
| | | 753 | | |
| | | 754 | | /// <inheritdoc cref="XML_SortSlow"/> |
| | | 755 | | public static void SortSlow<T, TGet, TSet, TCompare>(int start, int end, TGet get = default, TSet set = default, TComp |
| | | 756 | | where TCompare : struct, IFunc<T, T, CompareResult> |
| | | 757 | | where TGet : struct, IFunc<int, T> |
| | | 758 | | where TSet : struct, IAction<int, T> |
| | 62 | 759 | | { |
| | 62 | 760 | | SortSlowRecursive(start, end); |
| | | 761 | | void SortSlowRecursive(int i, int j) |
| | 5543 | 762 | | { |
| | 5543 | 763 | | if (i >= j) |
| | 3716 | 764 | | { |
| | 3716 | 765 | | return; |
| | | 766 | | } |
| | 1827 | 767 | | int mid = (i + j) / 2; |
| | 1827 | 768 | | SortSlowRecursive(i, mid); |
| | 1827 | 769 | | SortSlowRecursive(mid + 1, j); |
| | 1827 | 770 | | if (compare.Invoke(get.Invoke(j), get.Invoke(mid)) is Less) |
| | 583 | 771 | | { |
| | 583 | 772 | | Swap<T, TGet, TSet>(j, mid, get, set); |
| | 583 | 773 | | } |
| | 1827 | 774 | | SortSlowRecursive(i, j - 1); |
| | 5543 | 775 | | } |
| | 62 | 776 | | } |
| | | 777 | | |
| | | 778 | | /// <inheritdoc cref="XML_SortSlow"/> |
| | | 779 | | public static void SortSlow<T>(Span<T> span, Func<T, T, CompareResult>? compare = null) => |
| | 62 | 780 | | SortSlow<T, SFunc<T, T, CompareResult>>(span, compare ?? Compare); |
| | | 781 | | |
| | | 782 | | /// <inheritdoc cref="XML_SortSlow"/> |
| | | 783 | | public static void SortSlow<T, TCompare>(Span<T> span, TCompare compare = default) |
| | | 784 | | where TCompare : struct, IFunc<T, T, CompareResult> |
| | 62 | 785 | | { |
| | 62 | 786 | | SortSlowRecursive(span, 0, span.Length - 1); |
| | | 787 | | void SortSlowRecursive(Span<T> span, int i, int j) |
| | 5543 | 788 | | { |
| | 5543 | 789 | | if (i >= j) |
| | 3716 | 790 | | { |
| | 3716 | 791 | | return; |
| | | 792 | | } |
| | 1827 | 793 | | int mid = (i + j) / 2; |
| | 1827 | 794 | | SortSlowRecursive(span, i, mid); |
| | 1827 | 795 | | SortSlowRecursive(span, mid + 1, j); |
| | 1827 | 796 | | if (compare.Invoke(span[j], span[mid]) is Less) |
| | 583 | 797 | | { |
| | 583 | 798 | | Swap(ref span[j], ref span[mid]); |
| | 583 | 799 | | } |
| | 1827 | 800 | | SortSlowRecursive(span, i, j - 1); |
| | 5543 | 801 | | } |
| | 62 | 802 | | } |
| | | 803 | | |
| | | 804 | | #endregion |
| | | 805 | | |
| | | 806 | | #region SortGnome |
| | | 807 | | |
| | | 808 | | /// <summary>Sorts values using the gnome sort algorithm.</summary> |
| | | 809 | | /// <inheritdoc cref="XML_Sort"/> |
| | | 810 | | [Obsolete(NotIntended, true)] |
| | 1 | 811 | | public static void XML_SortGnome() => throw new DocumentationMethodException(); |
| | | 812 | | |
| | | 813 | | /// <inheritdoc cref="XML_SortGnome"/> |
| | | 814 | | public static void SortGnome<T>(int start, int end, Func<int, T> get, Action<int, T> set, Func<T, T, CompareResult>? c |
| | 83 | 815 | | SortGnome<T, SFunc<int, T>, SAction<int, T>, SFunc<T, T, CompareResult>>(start, end, get, set, compare ?? Compare); |
| | | 816 | | |
| | | 817 | | /// <inheritdoc cref="XML_SortGnome"/> |
| | | 818 | | public static void SortGnome<T, TGet, TSet, TCompare>(int start, int end, TGet get = default, TSet set = default, TCom |
| | | 819 | | where TCompare : struct, IFunc<T, T, CompareResult> |
| | | 820 | | where TGet : struct, IFunc<int, T> |
| | | 821 | | where TSet : struct, IAction<int, T> |
| | 83 | 822 | | { |
| | 83 | 823 | | int i = start; |
| | 5586224 | 824 | | while (i <= end) |
| | 5586141 | 825 | | { |
| | 5586141 | 826 | | if (i == start || compare.Invoke(get.Invoke(i), get.Invoke(i - 1)) != Less) |
| | 2799236 | 827 | | { |
| | 2799236 | 828 | | i++; |
| | 2799236 | 829 | | } |
| | | 830 | | else |
| | 2786905 | 831 | | { |
| | 2786905 | 832 | | Swap<T, TGet, TSet>(i, i - 1, get, set); |
| | 2786905 | 833 | | i--; |
| | 2786905 | 834 | | } |
| | 5586141 | 835 | | } |
| | 83 | 836 | | } |
| | | 837 | | |
| | | 838 | | /// <inheritdoc cref="XML_SortGnome"/> |
| | | 839 | | public static void SortGnome<T>(Span<T> span, Func<T, T, CompareResult>? compare = null) => |
| | 83 | 840 | | SortGnome<T, SFunc<T, T, CompareResult>>(span, compare ?? Compare); |
| | | 841 | | |
| | | 842 | | /// <inheritdoc cref="XML_SortGnome"/> |
| | | 843 | | public static void SortGnome<T, TCompare>(Span<T> span, TCompare compare = default) |
| | | 844 | | where TCompare : struct, IFunc<T, T, CompareResult> |
| | 83 | 845 | | { |
| | 83 | 846 | | int i = 0; |
| | 5586224 | 847 | | while (i < span.Length) |
| | 5586141 | 848 | | { |
| | 5586141 | 849 | | if (i is 0 || compare.Invoke(span[i], span[i - 1]) != Less) |
| | 2799236 | 850 | | { |
| | 2799236 | 851 | | i++; |
| | 2799236 | 852 | | } |
| | | 853 | | else |
| | 2786905 | 854 | | { |
| | 2786905 | 855 | | Swap(ref span[i], ref span[i - 1]); |
| | 2786905 | 856 | | i--; |
| | 2786905 | 857 | | } |
| | 5586141 | 858 | | } |
| | 83 | 859 | | } |
| | | 860 | | |
| | | 861 | | #endregion |
| | | 862 | | |
| | | 863 | | #region SortComb |
| | | 864 | | |
| | | 865 | | /// <summary>Sorts values using the comb sort algorithm.</summary> |
| | | 866 | | /// <inheritdoc cref="XML_Sort"/> |
| | | 867 | | [Obsolete(NotIntended, true)] |
| | 1 | 868 | | public static void XML_SortComb() => throw new DocumentationMethodException(); |
| | | 869 | | |
| | | 870 | | /// <inheritdoc cref="XML_SortComb"/> |
| | | 871 | | public static void SortComb<T>(int start, int end, Func<int, T> get, Action<int, T> set, Func<T, T, CompareResult>? co |
| | 83 | 872 | | SortComb<T, SFunc<int, T>, SAction<int, T>, SFunc<T, T, CompareResult>>(start, end, get, set, compare ?? Compare); |
| | | 873 | | |
| | | 874 | | /// <inheritdoc cref="XML_SortComb"/> |
| | | 875 | | public static void SortComb<T, TGet, TSet, TCompare>(int start, int end, TGet get = default, TSet set = default, TComp |
| | | 876 | | where TCompare : struct, IFunc<T, T, CompareResult> |
| | | 877 | | where TGet : struct, IFunc<int, T> |
| | | 878 | | where TSet : struct, IAction<int, T> |
| | 83 | 879 | | { |
| | | 880 | | const double shrink = 1.3; |
| | 83 | 881 | | int gap = end - start + 1; |
| | 83 | 882 | | bool sorted = false; |
| | 780 | 883 | | while (!sorted) |
| | 697 | 884 | | { |
| | 697 | 885 | | gap = (int)(gap / shrink); |
| | 697 | 886 | | if (gap <= 1) |
| | 197 | 887 | | { |
| | 197 | 888 | | gap = 1; |
| | 197 | 889 | | sorted = true; |
| | 197 | 890 | | } |
| | 525504 | 891 | | for (int i = start; i + gap <= end; i++) |
| | 262055 | 892 | | { |
| | 262055 | 893 | | if (compare.Invoke(get.Invoke(i), get.Invoke(i + gap)) is Greater) |
| | 52356 | 894 | | { |
| | 52356 | 895 | | Swap<T, TGet, TSet>(i, i + gap, get, set); |
| | 52356 | 896 | | sorted = false; |
| | 52356 | 897 | | } |
| | 262055 | 898 | | } |
| | 697 | 899 | | } |
| | 83 | 900 | | } |
| | | 901 | | |
| | | 902 | | /// <inheritdoc cref="XML_SortComb"/> |
| | | 903 | | public static void SortComb<T>(Span<T> span, Func<T, T, CompareResult>? compare = null) => |
| | 83 | 904 | | SortComb<T, SFunc<T, T, CompareResult>>(span, compare ?? Compare); |
| | | 905 | | |
| | | 906 | | /// <inheritdoc cref="XML_SortComb"/> |
| | | 907 | | public static void SortComb<T, TCompare>(Span<T> span, TCompare compare = default) |
| | | 908 | | where TCompare : struct, IFunc<T, T, CompareResult> |
| | 83 | 909 | | { |
| | | 910 | | const double shrink = 1.3; |
| | 83 | 911 | | int gap = span.Length; |
| | 83 | 912 | | bool sorted = false; |
| | 780 | 913 | | while (!sorted) |
| | 697 | 914 | | { |
| | 697 | 915 | | gap = (int)(gap / shrink); |
| | 697 | 916 | | if (gap <= 1) |
| | 197 | 917 | | { |
| | 197 | 918 | | gap = 1; |
| | 197 | 919 | | sorted = true; |
| | 197 | 920 | | } |
| | 525504 | 921 | | for (int i = 0; i + gap < span.Length; i++) |
| | 262055 | 922 | | { |
| | 262055 | 923 | | if (compare.Invoke(span[i], span[i + gap]) is Greater) |
| | 52356 | 924 | | { |
| | 52356 | 925 | | Swap(ref span[i], ref span[i + gap]); |
| | 52356 | 926 | | sorted = false; |
| | 52356 | 927 | | } |
| | 262055 | 928 | | } |
| | 697 | 929 | | } |
| | 83 | 930 | | } |
| | | 931 | | |
| | | 932 | | #endregion |
| | | 933 | | |
| | | 934 | | #region SortShell |
| | | 935 | | |
| | | 936 | | /// <summary>Sorts values using the shell sort algorithm.</summary> |
| | | 937 | | /// <inheritdoc cref="XML_Sort"/> |
| | | 938 | | [Obsolete(NotIntended, true)] |
| | 1 | 939 | | public static void XML_SortShell() => throw new DocumentationMethodException(); |
| | | 940 | | |
| | | 941 | | /// <inheritdoc cref="XML_SortShell"/> |
| | | 942 | | public static void SortShell<T>(int start, int end, Func<int, T> get, Action<int, T> set, Func<T, T, CompareResult>? c |
| | 83 | 943 | | SortShell<T, SFunc<int, T>, SAction<int, T>, SFunc<T, T, CompareResult>>(start, end, get, set, compare ?? Compare); |
| | | 944 | | |
| | | 945 | | /// <inheritdoc cref="XML_SortShell"/> |
| | | 946 | | public static void SortShell<T, TGet, TSet, TCompare>(int start, int end, TGet get = default, TSet set = default, TCom |
| | | 947 | | where TCompare : struct, IFunc<T, T, CompareResult> |
| | | 948 | | where TGet : struct, IFunc<int, T> |
| | | 949 | | where TSet : struct, IAction<int, T> |
| | 83 | 950 | | { |
| | 83 | 951 | | int[] gaps = { 701, 301, 132, 57, 23, 10, 4, 1 }; |
| | 1577 | 952 | | foreach (int gap in gaps) |
| | 664 | 953 | | { |
| | 159076 | 954 | | for (int i = gap + start; i <= end; i++) |
| | 78874 | 955 | | { |
| | 78874 | 956 | | T temp = get.Invoke(i); |
| | 78874 | 957 | | int j = i; |
| | 233930 | 958 | | for (; j >= gap + start && compare.Invoke(get.Invoke(j - gap), temp) is Greater; j -= gap) |
| | 77528 | 959 | | { |
| | 77528 | 960 | | set.Invoke(j, get.Invoke(j - gap)); |
| | 77528 | 961 | | } |
| | 78874 | 962 | | set.Invoke(j, temp); |
| | 78874 | 963 | | } |
| | 664 | 964 | | } |
| | 83 | 965 | | } |
| | | 966 | | |
| | | 967 | | /// <inheritdoc cref="XML_SortShell"/> |
| | | 968 | | public static void SortShell<T>(Span<T> span, Func<T, T, CompareResult>? compare = null) => |
| | 83 | 969 | | SortShell<T, SFunc<T, T, CompareResult>>(span, compare ?? Compare); |
| | | 970 | | |
| | | 971 | | /// <inheritdoc cref="XML_SortShell"/> |
| | | 972 | | public static void SortShell<T, TCompare>(Span<T> span, TCompare compare = default) |
| | | 973 | | where TCompare : struct, IFunc<T, T, CompareResult> |
| | 83 | 974 | | { |
| | 83 | 975 | | int[] gaps = { 701, 301, 132, 57, 23, 10, 4, 1 }; |
| | 1577 | 976 | | foreach (int gap in gaps) |
| | 664 | 977 | | { |
| | 159076 | 978 | | for (int i = gap; i < span.Length; i++) |
| | 78874 | 979 | | { |
| | 78874 | 980 | | T temp = span[i]; |
| | 78874 | 981 | | int j = i; |
| | 233930 | 982 | | for (; j >= gap && compare.Invoke(span[j - gap], temp) is Greater; j -= gap) |
| | 77528 | 983 | | { |
| | 77528 | 984 | | span[j] = span[j - gap]; |
| | 77528 | 985 | | } |
| | 78874 | 986 | | span[j] = temp; |
| | 78874 | 987 | | } |
| | 664 | 988 | | } |
| | 83 | 989 | | } |
| | | 990 | | |
| | | 991 | | #endregion |
| | | 992 | | |
| | | 993 | | #region SortCocktail |
| | | 994 | | |
| | | 995 | | /// <summary>Sorts values using the cocktail sort algorithm.</summary> |
| | | 996 | | /// <inheritdoc cref="XML_Sort"/> |
| | | 997 | | [Obsolete(NotIntended, true)] |
| | 1 | 998 | | public static void XML_SortCocktail() => throw new DocumentationMethodException(); |
| | | 999 | | |
| | | 1000 | | /// <inheritdoc cref="XML_SortCocktail"/> |
| | | 1001 | | public static void SortCocktail<T>(int start, int end, Func<int, T> get, Action<int, T> set, Func<T, T, CompareResult> |
| | 83 | 1002 | | SortCocktail<T, SFunc<int, T>, SAction<int, T>, SFunc<T, T, CompareResult>>(start, end, compare ?? Compare, get, set |
| | | 1003 | | |
| | | 1004 | | /// <inheritdoc cref="XML_SortCocktail"/> |
| | | 1005 | | public static void SortCocktail<T, TGet, TSet, TCompare>(int start, int end, TCompare compare = default, TGet get = de |
| | | 1006 | | where TCompare : struct, IFunc<T, T, CompareResult> |
| | | 1007 | | where TGet : struct, IFunc<int, T> |
| | | 1008 | | where TSet : struct, IAction<int, T> |
| | 83 | 1009 | | { |
| | 3243 | 1010 | | while (true) |
| | 3243 | 1011 | | { |
| | 3243 | 1012 | | bool swapped = false; |
| | 5690270 | 1013 | | for (int i = start; i <= end - 1; i++) |
| | 2841892 | 1014 | | { |
| | 2841892 | 1015 | | if (compare.Invoke(get.Invoke(i), get.Invoke(i + 1)) is Greater) |
| | 1389623 | 1016 | | { |
| | 1389623 | 1017 | | Swap<T, TGet, TSet>(i, i + 1, get, set); |
| | 1389623 | 1018 | | swapped = true; |
| | 1389623 | 1019 | | } |
| | 2841892 | 1020 | | } |
| | 3243 | 1021 | | if (!swapped) |
| | 42 | 1022 | | { |
| | 42 | 1023 | | break; |
| | | 1024 | | } |
| | 3201 | 1025 | | swapped = false; |
| | 5683262 | 1026 | | for (int i = end - 1; i >= start; i--) |
| | 2838430 | 1027 | | { |
| | 2838430 | 1028 | | if (compare.Invoke(get.Invoke(i), get.Invoke(i + 1)) is Greater) |
| | 1397282 | 1029 | | { |
| | 1397282 | 1030 | | Swap<T, TGet, TSet>(i, i + 1, get, set); |
| | 1397282 | 1031 | | swapped = true; |
| | 1397282 | 1032 | | } |
| | 2838430 | 1033 | | } |
| | 3201 | 1034 | | if (!swapped) |
| | 41 | 1035 | | { |
| | 41 | 1036 | | break; |
| | | 1037 | | } |
| | 3160 | 1038 | | } |
| | 83 | 1039 | | } |
| | | 1040 | | |
| | | 1041 | | /// <inheritdoc cref="XML_SortCocktail"/> |
| | | 1042 | | public static void SortCocktail<T>(Span<T> span, Func<T, T, CompareResult>? compare = null) => |
| | 83 | 1043 | | SortCocktail<T, SFunc<T, T, CompareResult>>(span, compare ?? Compare); |
| | | 1044 | | |
| | | 1045 | | /// <inheritdoc cref="XML_SortCocktail"/> |
| | | 1046 | | public static void SortCocktail<T, TCompare>(Span<T> span, TCompare compare = default) |
| | | 1047 | | where TCompare : struct, IFunc<T, T, CompareResult> |
| | 83 | 1048 | | { |
| | 3243 | 1049 | | while (true) |
| | 3243 | 1050 | | { |
| | 3243 | 1051 | | bool swapped = false; |
| | 5690270 | 1052 | | for (int i = 0; i < span.Length - 1; i++) |
| | 2841892 | 1053 | | { |
| | 2841892 | 1054 | | if (compare.Invoke(span[i], span[i + 1]) is Greater) |
| | 1389623 | 1055 | | { |
| | 1389623 | 1056 | | Swap(ref span[i], ref span[i + 1]); |
| | 1389623 | 1057 | | swapped = true; |
| | 1389623 | 1058 | | } |
| | 2841892 | 1059 | | } |
| | 3243 | 1060 | | if (!swapped) |
| | 42 | 1061 | | { |
| | 42 | 1062 | | break; |
| | | 1063 | | } |
| | 3201 | 1064 | | swapped = false; |
| | 5683262 | 1065 | | for (int i = span.Length - 2; i >= 0; i--) |
| | 2838430 | 1066 | | { |
| | 2838430 | 1067 | | if (compare.Invoke(span[i], span[i + 1]) is Greater) |
| | 1397282 | 1068 | | { |
| | 1397282 | 1069 | | Swap(ref span[i], ref span[i + 1]); |
| | 1397282 | 1070 | | swapped = true; |
| | 1397282 | 1071 | | } |
| | 2838430 | 1072 | | } |
| | 3201 | 1073 | | if (!swapped) |
| | 41 | 1074 | | { |
| | 41 | 1075 | | break; |
| | | 1076 | | } |
| | 3160 | 1077 | | } |
| | 83 | 1078 | | } |
| | | 1079 | | |
| | | 1080 | | #endregion |
| | | 1081 | | |
| | | 1082 | | #region SortCycle |
| | | 1083 | | |
| | | 1084 | | /// <summary>Sorts values using the cycle algorithm.</summary> |
| | | 1085 | | /// <inheritdoc cref="XML_Sort"/> |
| | | 1086 | | [Obsolete(NotIntended, true)] |
| | 1 | 1087 | | public static void XML_SortCycle() => throw new DocumentationMethodException(); |
| | | 1088 | | |
| | | 1089 | | /// <inheritdoc cref="XML_SortCycle"/> |
| | | 1090 | | public static void SortCycle<T>(int start, int end, Func<int, T> get, Action<int, T> set, Func<T, T, CompareResult>? c |
| | 83 | 1091 | | SortCycle<T, SFunc<int, T>, SAction<int, T>, SFunc<T, T, CompareResult>>(start, end, get, set, compare ?? Compare); |
| | | 1092 | | |
| | | 1093 | | /// <inheritdoc cref="XML_SortCycle"/> |
| | | 1094 | | public static void SortCycle<T, TGet, TSet, TCompare>(int start, int end, TGet get = default, TSet set = default, TCom |
| | | 1095 | | where TCompare : struct, IFunc<T, T, CompareResult> |
| | | 1096 | | where TGet : struct, IFunc<int, T> |
| | | 1097 | | where TSet : struct, IAction<int, T> |
| | 83 | 1098 | | { |
| | 24672 | 1099 | | for (int i = start; i < end; i++) |
| | 12253 | 1100 | | { |
| | 12253 | 1101 | | T pivot = get.Invoke(i); |
| | 12253 | 1102 | | int index = i; |
| | 11088126 | 1103 | | for (int j = i + 1; j <= end; j++) |
| | 5531810 | 1104 | | { |
| | 5531810 | 1105 | | if (compare.Invoke(get.Invoke(j), pivot) is Less) |
| | 30773 | 1106 | | { |
| | 30773 | 1107 | | index++; |
| | 30773 | 1108 | | } |
| | 5531810 | 1109 | | } |
| | 12253 | 1110 | | if (index == i) |
| | 12074 | 1111 | | { |
| | 12074 | 1112 | | continue; |
| | | 1113 | | } |
| | 179 | 1114 | | while (compare.Invoke(pivot, get.Invoke(index)) is Equal) |
| | 0 | 1115 | | { |
| | 0 | 1116 | | index++; |
| | 0 | 1117 | | } |
| | 179 | 1118 | | if (index != i) |
| | 179 | 1119 | | { |
| | 179 | 1120 | | T temp = pivot; |
| | 179 | 1121 | | pivot = get.Invoke(index); |
| | 179 | 1122 | | set.Invoke(index, temp); |
| | 179 | 1123 | | } |
| | 12270 | 1124 | | while (index != i) |
| | 12091 | 1125 | | { |
| | 12091 | 1126 | | index = i; |
| | 21916156 | 1127 | | for (int j = i + 1; j <= end; j++) |
| | 10945987 | 1128 | | { |
| | 10945987 | 1129 | | if (compare.Invoke(get.Invoke(j), pivot) is Less) |
| | 5443595 | 1130 | | { |
| | 5443595 | 1131 | | index++; |
| | 5443595 | 1132 | | } |
| | 10945987 | 1133 | | } |
| | 12127 | 1134 | | while (compare.Invoke(pivot, get.Invoke(index)) is Equal) |
| | 36 | 1135 | | { |
| | 36 | 1136 | | index += 1; |
| | 36 | 1137 | | } |
| | 12091 | 1138 | | if (compare.Invoke(pivot, get.Invoke(index)) is not Equal) |
| | 12091 | 1139 | | { |
| | 12091 | 1140 | | T temp = pivot; |
| | 12091 | 1141 | | pivot = get.Invoke(index); |
| | 12091 | 1142 | | set.Invoke(index, temp); |
| | 12091 | 1143 | | } |
| | 12091 | 1144 | | } |
| | 179 | 1145 | | } |
| | 83 | 1146 | | } |
| | | 1147 | | |
| | | 1148 | | /// <inheritdoc cref="XML_SortCycle"/> |
| | | 1149 | | public static void SortCycle<T>(Span<T> span, Func<T, T, CompareResult>? compare = null) => |
| | 83 | 1150 | | SortCycle<T, SFunc<T, T, CompareResult>>(span, compare ?? Compare); |
| | | 1151 | | |
| | | 1152 | | /// <inheritdoc cref="XML_SortCycle"/> |
| | | 1153 | | public static void SortCycle<T, TCompare>(Span<T> span, TCompare compare = default) |
| | | 1154 | | where TCompare : struct, IFunc<T, T, CompareResult> |
| | 83 | 1155 | | { |
| | 24672 | 1156 | | for (int i = 0; i < span.Length - 1; i++) |
| | 12253 | 1157 | | { |
| | 12253 | 1158 | | T pivot = span[i]; |
| | 12253 | 1159 | | int index = i; |
| | 11088126 | 1160 | | for (int j = i + 1; j < span.Length; j++) |
| | 5531810 | 1161 | | { |
| | 5531810 | 1162 | | if (compare.Invoke(span[j], pivot) is Less) |
| | 30773 | 1163 | | { |
| | 30773 | 1164 | | index++; |
| | 30773 | 1165 | | } |
| | 5531810 | 1166 | | } |
| | 12253 | 1167 | | if (index == i) |
| | 12074 | 1168 | | { |
| | 12074 | 1169 | | continue; |
| | | 1170 | | } |
| | 179 | 1171 | | while (compare.Invoke(pivot, span[index]) is Equal) |
| | 0 | 1172 | | { |
| | 0 | 1173 | | index++; |
| | 0 | 1174 | | } |
| | 179 | 1175 | | if (index != i) |
| | 179 | 1176 | | { |
| | 179 | 1177 | | Swap(ref span[index], ref pivot); |
| | 179 | 1178 | | } |
| | 12270 | 1179 | | while (index != i) |
| | 12091 | 1180 | | { |
| | 12091 | 1181 | | index = i; |
| | 21916156 | 1182 | | for (int j = i + 1; j < span.Length; j++) |
| | 10945987 | 1183 | | { |
| | 10945987 | 1184 | | if (compare.Invoke(span[j], pivot) is Less) |
| | 5443595 | 1185 | | { |
| | 5443595 | 1186 | | index++; |
| | 5443595 | 1187 | | } |
| | 10945987 | 1188 | | } |
| | 12127 | 1189 | | while (compare.Invoke(pivot, span[index]) is Equal) |
| | 36 | 1190 | | { |
| | 36 | 1191 | | index += 1; |
| | 36 | 1192 | | } |
| | 12091 | 1193 | | if (compare.Invoke(pivot, span[index]) is not Equal) |
| | 12091 | 1194 | | { |
| | 12091 | 1195 | | Swap(ref span[index], ref pivot); |
| | 12091 | 1196 | | } |
| | 12091 | 1197 | | } |
| | 179 | 1198 | | } |
| | 83 | 1199 | | } |
| | | 1200 | | |
| | | 1201 | | #endregion |
| | | 1202 | | |
| | | 1203 | | #region SortPancake |
| | | 1204 | | |
| | | 1205 | | /// <summary>Sorts values using the pancake algorithm.</summary> |
| | | 1206 | | /// <inheritdoc cref="XML_Sort"/> |
| | | 1207 | | [Obsolete(NotIntended, true)] |
| | 1 | 1208 | | public static void XML_SortPancake() => throw new DocumentationMethodException(); |
| | | 1209 | | |
| | | 1210 | | /// <inheritdoc cref="XML_SortPancake"/> |
| | | 1211 | | public static void SortPancake<T>(int start, int end, Func<int, T> get, Action<int, T> set, Func<T, T, CompareResult>? |
| | 83 | 1212 | | SortPancake<T, SFunc<int, T>, SAction<int, T>, SFunc<T, T, CompareResult>>(start, end, get, set, compare ?? Compare) |
| | | 1213 | | |
| | | 1214 | | /// <inheritdoc cref="XML_SortPancake"/> |
| | | 1215 | | public static void SortPancake<T, TGet, TSet, TCompare>(int start, int end, TGet get = default, TSet set = default, TC |
| | | 1216 | | where TCompare : struct, IFunc<T, T, CompareResult> |
| | | 1217 | | where TGet : struct, IFunc<int, T> |
| | | 1218 | | where TSet : struct, IAction<int, T> |
| | 83 | 1219 | | { |
| | 24672 | 1220 | | for (int i = end; i > start; i--) |
| | 12253 | 1221 | | { |
| | 12253 | 1222 | | int index = MaximumIndex<T, TGet, TCompare>(start, i, get, compare); |
| | 12253 | 1223 | | if (index != i) |
| | 12074 | 1224 | | { |
| | 12074 | 1225 | | Reverse<T, TGet, TSet>(start, index, get, set); |
| | 12074 | 1226 | | Reverse<T, TGet, TSet>(start, i, get, set); |
| | 12074 | 1227 | | } |
| | 12253 | 1228 | | } |
| | 83 | 1229 | | } |
| | | 1230 | | |
| | | 1231 | | /// <inheritdoc cref="XML_SortPancake"/> |
| | | 1232 | | public static void SortPancake<T>(Span<T> span, Func<T, T, CompareResult>? compare = null) => |
| | 83 | 1233 | | SortPancake<T, SFunc<T, T, CompareResult>>(span, compare ?? Compare); |
| | | 1234 | | |
| | | 1235 | | /// <inheritdoc cref="XML_SortPancake"/> |
| | | 1236 | | public static void SortPancake<T, TCompare>(Span<T> span, TCompare compare = default) |
| | | 1237 | | where TCompare : struct, IFunc<T, T, CompareResult> |
| | 83 | 1238 | | { |
| | 24672 | 1239 | | for (int i = span.Length; i > 1; i--) |
| | 12253 | 1240 | | { |
| | 12253 | 1241 | | int index = MaximumIndex<T, TCompare>(span[0..i], compare); |
| | 12253 | 1242 | | if (index != i - 1) |
| | 12074 | 1243 | | { |
| | 12074 | 1244 | | span[0..(index + 1)].Reverse(); |
| | 12074 | 1245 | | span[0..i].Reverse(); |
| | 12074 | 1246 | | } |
| | 12253 | 1247 | | } |
| | 83 | 1248 | | } |
| | | 1249 | | |
| | | 1250 | | #endregion |
| | | 1251 | | |
| | | 1252 | | #region SortStooge |
| | | 1253 | | |
| | | 1254 | | /// <summary>Sorts values using the stooge algorithm.</summary> |
| | | 1255 | | /// <inheritdoc cref="XML_Sort"/> |
| | | 1256 | | [Obsolete(NotIntended, true)] |
| | 1 | 1257 | | public static void XML_SortStooge() => throw new DocumentationMethodException(); |
| | | 1258 | | |
| | | 1259 | | /// <inheritdoc cref="XML_SortStooge"/> |
| | | 1260 | | public static void SortStooge<T>(int start, int end, Func<int, T> get, Action<int, T> set, Func<T, T, CompareResult>? |
| | 67 | 1261 | | SortStooge<T, SFunc<int, T>, SAction<int, T>, SFunc<T, T, CompareResult>>(start, end, get, set, compare ?? Compare); |
| | | 1262 | | |
| | | 1263 | | /// <inheritdoc cref="XML_SortPancake"/> |
| | | 1264 | | public static void SortStooge<T, TGet, TSet, TCompare>(int start, int end, TGet get = default, TSet set = default, TCo |
| | | 1265 | | where TCompare : struct, IFunc<T, T, CompareResult> |
| | | 1266 | | where TGet : struct, IFunc<int, T> |
| | | 1267 | | where TSet : struct, IAction<int, T> |
| | 1334635 | 1268 | | { |
| | 1334635 | 1269 | | int n = end - start + 1; |
| | 1334635 | 1270 | | if (n < 2) |
| | 10 | 1271 | | { |
| | 10 | 1272 | | return; |
| | | 1273 | | } |
| | 1334625 | 1274 | | if (compare.Invoke(get.Invoke(start), get.Invoke(end)) is Greater) |
| | 12426 | 1275 | | { |
| | 12426 | 1276 | | Swap<T, TGet, TSet>(start, end, get, set); |
| | 12426 | 1277 | | } |
| | 1334625 | 1278 | | if (n > 2) |
| | 444856 | 1279 | | { |
| | 444856 | 1280 | | int third = n / 3; |
| | 444856 | 1281 | | SortStooge<T, TGet, TSet, TCompare>(start, end - third, get, set, compare); |
| | 444856 | 1282 | | SortStooge<T, TGet, TSet, TCompare>(start + third, end, get, set, compare); |
| | 444856 | 1283 | | SortStooge<T, TGet, TSet, TCompare>(start, end - third, get, set, compare); |
| | 444856 | 1284 | | } |
| | 1334635 | 1285 | | } |
| | | 1286 | | |
| | | 1287 | | /// <inheritdoc cref="XML_SortStooge"/> |
| | | 1288 | | public static void SortStooge<T>(Span<T> span, Func<T, T, CompareResult>? compare = null) => |
| | 67 | 1289 | | SortStooge<T, SFunc<T, T, CompareResult>>(span, compare ?? Compare); |
| | | 1290 | | |
| | | 1291 | | /// <inheritdoc cref="XML_SortStooge"/> |
| | | 1292 | | public static void SortStooge<T, TCompare>(Span<T> span, TCompare compare = default) |
| | | 1293 | | where TCompare : struct, IFunc<T, T, CompareResult> |
| | 1334635 | 1294 | | { |
| | 1334635 | 1295 | | if (span.Length < 2) |
| | 10 | 1296 | | { |
| | 10 | 1297 | | return; |
| | | 1298 | | } |
| | 1334625 | 1299 | | if (compare.Invoke(span[0], span[^1]) is Greater) |
| | 12458 | 1300 | | { |
| | 12458 | 1301 | | Swap(ref span[0], ref span[^1]); |
| | 12458 | 1302 | | } |
| | 1334625 | 1303 | | if (span.Length > 2) |
| | 444856 | 1304 | | { |
| | 444856 | 1305 | | int third = span.Length / 3; |
| | 444856 | 1306 | | SortStooge(span[third..], compare); |
| | 444856 | 1307 | | SortStooge(span[..^third], compare); |
| | 444856 | 1308 | | SortStooge(span[third..], compare); |
| | 444856 | 1309 | | } |
| | 1334635 | 1310 | | } |
| | | 1311 | | |
| | | 1312 | | #endregion |
| | | 1313 | | |
| | | 1314 | | #region SortTim |
| | | 1315 | | |
| | | 1316 | | /// <summary> |
| | | 1317 | | /// Sorts values using the Tim sort algorithm.<br/> |
| | | 1318 | | /// Runtime: Ω(n), ε(n*ln(n)), O(n*ln(n))<br/> |
| | | 1319 | | /// Memory: O(n)<br/> |
| | | 1320 | | /// Stable: True |
| | | 1321 | | /// </summary> |
| | | 1322 | | /// <inheritdoc cref="XML_Sort"/> |
| | | 1323 | | [Obsolete(NotIntended, true)] |
| | 1 | 1324 | | public static void XML_SortTim() => throw new DocumentationMethodException(); |
| | | 1325 | | |
| | | 1326 | | /// <inheritdoc cref="XML_SortHeap"/> |
| | | 1327 | | public static void SortTim<T>(int start, int end, Func<int, T> get, Action<int, T> set, Func<T, T, CompareResult>? com |
| | 83 | 1328 | | SortTim<T, SFunc<int, T>, SAction<int, T>, SFunc<T, T, CompareResult>>(start, end, get, set, compare ?? Compare); |
| | | 1329 | | |
| | | 1330 | | /// <inheritdoc cref="XML_SortTim"/> |
| | | 1331 | | public static void SortTim<T, TGet, TSet, TCompare>(int start, int end, TGet get = default, TSet set = default, TCompa |
| | | 1332 | | where TCompare : struct, IFunc<T, T, CompareResult> |
| | | 1333 | | where TGet : struct, IFunc<int, T> |
| | | 1334 | | where TSet : struct, IAction<int, T> |
| | 83 | 1335 | | { |
| | | 1336 | | const int block = 32; |
| | 83 | 1337 | | int n = end - start + 1; |
| | 1062 | 1338 | | for (int i = start; i < n; i += block) |
| | 448 | 1339 | | { |
| | 448 | 1340 | | SortInsertion<T, TGet, TSet, TCompare>(i, Math.Min(i + block, start + n - 1), get, set, compare); |
| | 448 | 1341 | | } |
| | 316 | 1342 | | for (int size = block; size < n; size *= 2) |
| | 75 | 1343 | | { |
| | 892 | 1344 | | for (int left = start; left < n; left += 2 * size) |
| | 371 | 1345 | | { |
| | 371 | 1346 | | int mid = left + size - 1; |
| | 371 | 1347 | | int right = Math.Min(left + 2 * size, n + start) - 1; |
| | 371 | 1348 | | if (mid < right) |
| | 370 | 1349 | | { |
| | | 1350 | | // Merge |
| | 370 | 1351 | | Span<T> a = new T[mid - left + 1]; |
| | 370 | 1352 | | Span<T> b = new T[right - mid]; |
| | 59556 | 1353 | | for (int i = 0; i < a.Length; i++) |
| | 29408 | 1354 | | { |
| | 29408 | 1355 | | a[i] = get.Invoke(left + i); |
| | 29408 | 1356 | | } |
| | 55762 | 1357 | | for (int i = 0; i < b.Length; i++) |
| | 27511 | 1358 | | { |
| | 27511 | 1359 | | b[i] = get.Invoke(mid + 1 + i); |
| | 27511 | 1360 | | } |
| | 370 | 1361 | | int ai = 0; // index of a |
| | 370 | 1362 | | int bi = 0; // index of b |
| | 370 | 1363 | | int si = left; // index of span |
| | 112762 | 1364 | | for (; ai < a.Length && bi < b.Length; si++) |
| | 56196 | 1365 | | { |
| | 56196 | 1366 | | if (compare.Invoke(a[ai], b[bi]) is not Greater) |
| | 29119 | 1367 | | { |
| | 29119 | 1368 | | set.Invoke(si, a[ai]); |
| | 29119 | 1369 | | ai++; |
| | 29119 | 1370 | | } |
| | | 1371 | | else |
| | 27077 | 1372 | | { |
| | 27077 | 1373 | | set.Invoke(si, b[bi]); |
| | 27077 | 1374 | | bi++; |
| | 27077 | 1375 | | } |
| | 56196 | 1376 | | } |
| | 1237 | 1377 | | for (; ai < a.Length; si++, ai++) |
| | 289 | 1378 | | { |
| | 289 | 1379 | | set.Invoke(si, a[ai]); |
| | 289 | 1380 | | } |
| | 1672 | 1381 | | for (; bi < b.Length; si++, bi++) |
| | 434 | 1382 | | { |
| | 434 | 1383 | | set.Invoke(si, b[bi]); |
| | 434 | 1384 | | } |
| | 370 | 1385 | | } |
| | 371 | 1386 | | } |
| | 75 | 1387 | | } |
| | 83 | 1388 | | } |
| | | 1389 | | |
| | | 1390 | | /// <inheritdoc cref="XML_SortTim"/> |
| | | 1391 | | public static void SortTim<T>(Span<T> span, Func<T, T, CompareResult>? compare = null) => |
| | 83 | 1392 | | SortTim<T, SFunc<T, T, CompareResult>>(span, compare ?? Compare); |
| | | 1393 | | |
| | | 1394 | | /// <inheritdoc cref="XML_SortTim"/> |
| | | 1395 | | public static void SortTim<T, TCompare>(Span<T> span, TCompare compare = default) |
| | | 1396 | | where TCompare : struct, IFunc<T, T, CompareResult> |
| | 83 | 1397 | | { |
| | | 1398 | | const int block = 32; |
| | 1062 | 1399 | | for (int i = 0; i < span.Length; i += block) |
| | 448 | 1400 | | { |
| | 448 | 1401 | | SortInsertion(span[i..Math.Min(i + block, span.Length)], compare); |
| | 448 | 1402 | | } |
| | 316 | 1403 | | for (int size = block; size < span.Length; size *= 2) |
| | 75 | 1404 | | { |
| | 892 | 1405 | | for (int left = 0; left < span.Length; left += 2 * size) |
| | 371 | 1406 | | { |
| | 371 | 1407 | | int mid = left + size - 1; |
| | 371 | 1408 | | int right = Math.Min(left + 2 * size, span.Length); |
| | 371 | 1409 | | if (mid < right) |
| | 370 | 1410 | | { |
| | | 1411 | | // Merge |
| | 370 | 1412 | | Span<T> a = span[left..(mid + 1)].ToArray(); |
| | 370 | 1413 | | Span<T> b = span[(mid + 1)..right].ToArray(); |
| | 370 | 1414 | | int ai = 0; // index of a |
| | 370 | 1415 | | int bi = 0; // index of b |
| | 370 | 1416 | | int si = left; // index of span |
| | 112606 | 1417 | | for (; ai < a.Length && bi < b.Length; si++) |
| | 56118 | 1418 | | { |
| | 56118 | 1419 | | if (compare.Invoke(a[ai], b[bi]) is not Greater) |
| | 28858 | 1420 | | { |
| | 28858 | 1421 | | span[si] = a[ai]; |
| | 28858 | 1422 | | ai++; |
| | 28858 | 1423 | | } |
| | | 1424 | | else |
| | 27260 | 1425 | | { |
| | 27260 | 1426 | | span[si] = b[bi]; |
| | 27260 | 1427 | | bi++; |
| | 27260 | 1428 | | } |
| | 56118 | 1429 | | } |
| | 2020 | 1430 | | for (; ai < a.Length; si++, ai++) |
| | 550 | 1431 | | { |
| | 550 | 1432 | | span[si] = a[ai]; |
| | 550 | 1433 | | } |
| | 1123 | 1434 | | for (; bi < b.Length; si++, bi++) |
| | 251 | 1435 | | { |
| | 251 | 1436 | | span[si] = b[bi]; |
| | 251 | 1437 | | } |
| | 370 | 1438 | | } |
| | 371 | 1439 | | } |
| | 75 | 1440 | | } |
| | 83 | 1441 | | } |
| | | 1442 | | |
| | | 1443 | | #endregion |
| | | 1444 | | |
| | | 1445 | | #region SortCounting |
| | | 1446 | | |
| | | 1447 | | /// <inheritdoc cref="SortCounting{T, TSelect, TGet, TSet}(int, int, TSelect, TGet, TSet)"/> |
| | | 1448 | | public static void SortCounting(int start, int end, Func<int, uint> get, Action<int, uint> set) |
| | 0 | 1449 | | { |
| | 0 | 1450 | | if (get is null) throw new ArgumentNullException(nameof(get)); |
| | 0 | 1451 | | if (set is null) throw new ArgumentNullException(nameof(set)); |
| | 0 | 1452 | | SortCounting<uint, Identity<uint>, SFunc<int, uint>, SAction<int, uint>>(start, end, default, get, set); |
| | 0 | 1453 | | } |
| | | 1454 | | |
| | | 1455 | | /// <inheritdoc cref="SortCounting{T, TSelect, TGet, TSet}(int, int, TSelect, TGet, TSet)"/> |
| | | 1456 | | public static void SortCounting<T>(int start, int end, Func<T, uint> select, Func<int, T> get, Action<int, T> set) |
| | 35 | 1457 | | { |
| | 35 | 1458 | | if (select is null) throw new ArgumentNullException(nameof(select)); |
| | 35 | 1459 | | if (get is null) throw new ArgumentNullException(nameof(get)); |
| | 35 | 1460 | | if (set is null) throw new ArgumentNullException(nameof(set)); |
| | 35 | 1461 | | SortCounting<T, SFunc<T, uint>, SFunc<int, T>, SAction<int, T>>(start, end, select, get, set); |
| | 35 | 1462 | | } |
| | | 1463 | | |
| | | 1464 | | /// <inheritdoc cref="SortCounting{T, TSelect, TGet, TSet}(int, int, TSelect, TGet, TSet)"/> |
| | | 1465 | | public static void SortCounting<TGet, TSet>(int start, int end, TGet get = default, TSet set = default) |
| | | 1466 | | where TGet : struct, IFunc<int, uint> |
| | | 1467 | | where TSet : struct, IAction<int, uint> => |
| | 0 | 1468 | | SortCounting<uint, Identity<uint>, TGet, TSet>(start, end, default, get, set); |
| | | 1469 | | |
| | | 1470 | | /// <summary> |
| | | 1471 | | /// Sorts values using the counting sort algorithm.<br/> |
| | | 1472 | | /// Runtime: Θ(Max(<paramref name="select"/>(n)))<br/> |
| | | 1473 | | /// Memory: Θ(Max(<paramref name="select"/>(n)))<br/> |
| | | 1474 | | /// Stable: True |
| | | 1475 | | /// </summary> |
| | | 1476 | | /// <typeparam name="T">The type of values to sort.</typeparam> |
| | | 1477 | | /// <typeparam name="TSelect">The type of method for selecting an <see cref="int"/> values from <typeparamref name="T" |
| | | 1478 | | /// <typeparam name="TGet">The type of get function.</typeparam> |
| | | 1479 | | /// <typeparam name="TSet">The type of set function.</typeparam> |
| | | 1480 | | /// <param name="start">The starting index of the sort.</param> |
| | | 1481 | | /// <param name="end">The ending index of the sort.</param> |
| | | 1482 | | /// <param name="select">The method for selecting <see cref="int"/> values from <typeparamref name="T"/> values.</para |
| | | 1483 | | /// <param name="get">The get function.</param> |
| | | 1484 | | /// <param name="set">The set function.</param> |
| | | 1485 | | public static void SortCounting<T, TSelect, TGet, TSet>(int start, int end, TSelect select = default, TGet get = defau |
| | | 1486 | | where TSelect : struct, IFunc<T, uint> |
| | | 1487 | | where TGet : struct, IFunc<int, T> |
| | | 1488 | | where TSet : struct, IAction<int, T> |
| | 35 | 1489 | | { |
| | 35 | 1490 | | if (end - start + 1 < 2) |
| | 4 | 1491 | | { |
| | 4 | 1492 | | return; |
| | | 1493 | | } |
| | 31 | 1494 | | Span<T> sortingSpan = new T[end - start + 1]; |
| | 31 | 1495 | | uint max = 0; |
| | 11112 | 1496 | | for (int i = start; i <= end; i++) |
| | 5525 | 1497 | | { |
| | 5525 | 1498 | | uint temp = select.Invoke(get.Invoke(i)); |
| | 5525 | 1499 | | max = Math.Max(max, temp); |
| | 5525 | 1500 | | } |
| | 31 | 1501 | | SortCounting(start, end, select, get, set, sortingSpan, max); |
| | 35 | 1502 | | } |
| | | 1503 | | |
| | | 1504 | | internal static void SortCounting<T, TSelect, TGet, TSet>(int start, int end, TSelect select, TGet get, TSet set, Span |
| | | 1505 | | where TSelect : struct, IFunc<T, uint> |
| | | 1506 | | where TGet : struct, IFunc<int, T> |
| | | 1507 | | where TSet : struct, IAction<int, T> |
| | 132 | 1508 | | { |
| | 132 | 1509 | | if (end - start + 1 != sortingSpan.Length) |
| | 0 | 1510 | | { |
| | 0 | 1511 | | throw new TowelBugException(message: $"{nameof(end)} - {nameof(start)} + 1 != {nameof(sortingSpan)}.{nameof(sortin |
| | | 1512 | | } |
| | 132 | 1513 | | int[] count = new int[max + 1]; |
| | 57276 | 1514 | | for (int i = start; i <= end; i++) |
| | 28506 | 1515 | | { |
| | 28506 | 1516 | | count[select.Invoke(get.Invoke(i))]++; |
| | 28506 | 1517 | | } |
| | 15677552 | 1518 | | for (int i = 1; i <= max; i++) |
| | 7838644 | 1519 | | { |
| | 7838644 | 1520 | | count[i] += count[i - 1]; |
| | 7838644 | 1521 | | } |
| | 57276 | 1522 | | for (int i = end; i >= start; i--) |
| | 28506 | 1523 | | { |
| | 28506 | 1524 | | sortingSpan[count[select.Invoke(get.Invoke(i))] - 1] = get.Invoke(i); |
| | 28506 | 1525 | | count[select.Invoke(get.Invoke(i))]--; |
| | 28506 | 1526 | | } |
| | 85914 | 1527 | | for (int a = start, b = 0; a <= end; a++, b++) |
| | 28506 | 1528 | | { |
| | 28506 | 1529 | | set.Invoke(a, sortingSpan[b]); |
| | 28506 | 1530 | | } |
| | 132 | 1531 | | } |
| | | 1532 | | |
| | | 1533 | | /// <inheritdoc cref="SortCounting{T, TGetKey}(Span{T}, TGetKey)"/> |
| | | 1534 | | public static void SortCounting(Span<uint> span) => |
| | 0 | 1535 | | SortCounting<uint, Identity<uint>>(span); |
| | | 1536 | | |
| | | 1537 | | /// <inheritdoc cref="SortCounting{T, TGetKey}(Span{T}, TGetKey)"/> |
| | | 1538 | | public static void SortCounting<T>(Span<T> span, Func<T, uint> select) => |
| | 35 | 1539 | | SortCounting<T, SFunc<T, uint>>(span, select); |
| | | 1540 | | |
| | | 1541 | | /// <summary> |
| | | 1542 | | /// Sorts values using the counting sort algorithm.<br/> |
| | | 1543 | | /// Runtime: Θ(Max(<paramref name="select"/>(<paramref name="span"/>)))<br/> |
| | | 1544 | | /// Memory: Θ(Max(<paramref name="select"/>(<paramref name="span"/>)))<br/> |
| | | 1545 | | /// Stable: True |
| | | 1546 | | /// </summary> |
| | | 1547 | | /// <typeparam name="T">The type of values to sort.</typeparam> |
| | | 1548 | | /// <typeparam name="TSelect">The type of method for selecting an <see cref="int"/> values from <typeparamref name="T" |
| | | 1549 | | /// <param name="span">The span to be sorted.</param> |
| | | 1550 | | /// <param name="select">The method for selecting <see cref="int"/> values from <typeparamref name="T"/> values.</para |
| | | 1551 | | public static void SortCounting<T, TSelect>(Span<T> span, TSelect select = default) |
| | | 1552 | | where TSelect : struct, IFunc<T, uint> |
| | 35 | 1553 | | { |
| | 35 | 1554 | | if (span.Length < 2) |
| | 4 | 1555 | | { |
| | 4 | 1556 | | return; |
| | | 1557 | | } |
| | 31 | 1558 | | Span<T> sortingSpan = new T[span.Length]; |
| | 31 | 1559 | | uint max = uint.MinValue; |
| | 11143 | 1560 | | foreach (T t in span) |
| | 5525 | 1561 | | { |
| | 5525 | 1562 | | uint temp = select.Invoke(t); |
| | 5525 | 1563 | | max = Math.Max(max, temp); |
| | 5525 | 1564 | | } |
| | 31 | 1565 | | SortCounting(span, select, sortingSpan, max); |
| | 35 | 1566 | | } |
| | | 1567 | | |
| | | 1568 | | internal static void SortCounting<T, TSelect>(Span<T> span, TSelect select, Span<T> sortingSpan, uint max) |
| | | 1569 | | where TSelect : struct, IFunc<T, uint> |
| | 132 | 1570 | | { |
| | 132 | 1571 | | if (span.Length != sortingSpan.Length) |
| | 0 | 1572 | | { |
| | 0 | 1573 | | throw new TowelBugException(message: $"{nameof(span)}.{nameof(span.Length)} != {nameof(sortingSpan)}.{nameof(sorti |
| | | 1574 | | } |
| | 132 | 1575 | | int[] count = new int[max + 1]; |
| | 57276 | 1576 | | for (int i = 0; i < span.Length; i++) |
| | 28506 | 1577 | | { |
| | 28506 | 1578 | | count[select.Invoke(span[i])]++; |
| | 28506 | 1579 | | } |
| | 15677552 | 1580 | | for (int i = 1; i <= max; i++) |
| | 7838644 | 1581 | | { |
| | 7838644 | 1582 | | count[i] += count[i - 1]; |
| | 7838644 | 1583 | | } |
| | 57276 | 1584 | | for (int i = span.Length - 1; i >= 0; i--) |
| | 28506 | 1585 | | { |
| | 28506 | 1586 | | sortingSpan[count[select.Invoke(span[i])] - 1] = span[i]; |
| | 28506 | 1587 | | count[select.Invoke(span[i])]--; |
| | 28506 | 1588 | | } |
| | 132 | 1589 | | sortingSpan.CopyTo(span); |
| | 132 | 1590 | | } |
| | | 1591 | | |
| | | 1592 | | #endregion |
| | | 1593 | | |
| | | 1594 | | #region SortRadix |
| | | 1595 | | |
| | | 1596 | | /// <inheritdoc cref="SortRadix{T, TSelect, TGet, TSet}(int, int, TSelect, TGet, TSet)"/> |
| | | 1597 | | public static void SortRadix(int start, int end, Func<int, uint> get, Action<int, uint> set) |
| | 0 | 1598 | | { |
| | 0 | 1599 | | if (get is null) throw new ArgumentNullException(nameof(get)); |
| | 0 | 1600 | | if (set is null) throw new ArgumentNullException(nameof(set)); |
| | 0 | 1601 | | SortRadix<uint, Identity<uint>, SFunc<int, uint>, SAction<int, uint>>(start, end, default, get, set); |
| | 0 | 1602 | | } |
| | | 1603 | | |
| | | 1604 | | /// <inheritdoc cref="SortRadix{T, TSelect, TGet, TSet}(int, int, TSelect, TGet, TSet)"/> |
| | | 1605 | | public static void SortRadix<T>(int start, int end, Func<T, uint> select, Func<int, T> get, Action<int, T> set) |
| | 35 | 1606 | | { |
| | 35 | 1607 | | if (select is null) throw new ArgumentNullException(nameof(select)); |
| | 35 | 1608 | | if (get is null) throw new ArgumentNullException(nameof(get)); |
| | 35 | 1609 | | if (set is null) throw new ArgumentNullException(nameof(set)); |
| | 35 | 1610 | | SortRadix<T, SFunc<T, uint>, SFunc<int, T>, SAction<int, T>>(start, end, select, get, set); |
| | 35 | 1611 | | } |
| | | 1612 | | |
| | | 1613 | | /// <inheritdoc cref="SortRadix{T, TSelect, TGet, TSet}(int, int, TSelect, TGet, TSet)"/> |
| | | 1614 | | public static void SortRadix<TGet, TSet>(int start, int end, TGet get = default, TSet set = default) |
| | | 1615 | | where TGet : struct, IFunc<int, uint> |
| | | 1616 | | where TSet : struct, IAction<int, uint> => |
| | 0 | 1617 | | SortRadix<uint, Identity<uint>, TGet, TSet>(start, end, default, get, set); |
| | | 1618 | | |
| | | 1619 | | /// <summary> |
| | | 1620 | | /// Sorts values using the radix sort algorithm. |
| | | 1621 | | /// </summary> |
| | | 1622 | | /// <typeparam name="T">The type of values to sort.</typeparam> |
| | | 1623 | | /// <typeparam name="TSelect">The type of method for selecting an <see cref="int"/> values from <typeparamref name="T" |
| | | 1624 | | /// <typeparam name="TGet">The type of get function.</typeparam> |
| | | 1625 | | /// <typeparam name="TSet">The type of set function.</typeparam> |
| | | 1626 | | /// <param name="start">The starting index of the sort.</param> |
| | | 1627 | | /// <param name="end">The ending index of the sort.</param> |
| | | 1628 | | /// <param name="select">The method for selecting <see cref="int"/> values from <typeparamref name="T"/> values.</para |
| | | 1629 | | /// <param name="get">The get function.</param> |
| | | 1630 | | /// <param name="set">The set function.</param> |
| | | 1631 | | public static void SortRadix<T, TSelect, TGet, TSet>(int start, int end, TSelect select = default, TGet get = default, |
| | | 1632 | | where TSelect : struct, IFunc<T, uint> |
| | | 1633 | | where TGet : struct, IFunc<int, T> |
| | | 1634 | | where TSet : struct, IAction<int, T> |
| | 35 | 1635 | | { |
| | 35 | 1636 | | if (end - start + 1 < 2) |
| | 4 | 1637 | | { |
| | 4 | 1638 | | return; |
| | | 1639 | | } |
| | 31 | 1640 | | uint max = uint.MinValue; |
| | 11112 | 1641 | | for (int i = start; i <= end; i++) |
| | 5525 | 1642 | | { |
| | 5525 | 1643 | | uint temp = select.Invoke(get.Invoke(i)); |
| | 5525 | 1644 | | max = Math.Max(max, temp); |
| | 5525 | 1645 | | } |
| | 31 | 1646 | | Span<T> sortingSpan = new T[end - start + 1]; |
| | 264 | 1647 | | for (uint divisor = 1; max / divisor > 0; divisor *= 10) |
| | 101 | 1648 | | { |
| | 101 | 1649 | | SortCounting<T, SortRadixSelect<T, TSelect>, TGet, TSet>(start, end, new() { Select = select, Divisor = divisor }, |
| | 101 | 1650 | | } |
| | 35 | 1651 | | } |
| | | 1652 | | |
| | | 1653 | | /// <inheritdoc cref="SortRadix{T, TGetKey}(Span{T}, TGetKey)"/> |
| | | 1654 | | public static void SortRadix(Span<uint> span) => |
| | 0 | 1655 | | SortRadix<uint, Identity<uint>>(span); |
| | | 1656 | | |
| | | 1657 | | /// <inheritdoc cref="SortRadix{T, TGetKey}(Span{T}, TGetKey)"/> |
| | | 1658 | | public static void SortRadix<T>(Span<T> span, Func<T, uint> select) => |
| | 35 | 1659 | | SortRadix<T, SFunc<T, uint>>(span, select); |
| | | 1660 | | |
| | | 1661 | | /// <summary> |
| | | 1662 | | /// Sorts values using the radix sort algorithm. |
| | | 1663 | | /// </summary> |
| | | 1664 | | /// <typeparam name="T">The type of values to sort.</typeparam> |
| | | 1665 | | /// <typeparam name="TSelect">The type of method for selecting an <see cref="int"/> values from <typeparamref name="T" |
| | | 1666 | | /// <param name="span">The span to be sorted.</param> |
| | | 1667 | | /// <param name="select">The method for selecting <see cref="int"/> values from <typeparamref name="T"/> values.</para |
| | | 1668 | | public static void SortRadix<T, TSelect>(Span<T> span, TSelect select = default) |
| | | 1669 | | where TSelect : struct, IFunc<T, uint> |
| | 35 | 1670 | | { |
| | 35 | 1671 | | if (span.Length < 2) |
| | 4 | 1672 | | { |
| | 4 | 1673 | | return; |
| | | 1674 | | } |
| | 31 | 1675 | | uint max = uint.MinValue; |
| | 11143 | 1676 | | foreach (T t in span) |
| | 5525 | 1677 | | { |
| | 5525 | 1678 | | uint temp = select.Invoke(t); |
| | 5525 | 1679 | | if (temp < 0) |
| | 0 | 1680 | | { |
| | 0 | 1681 | | throw new ArgumentException(message: $"a value exists in {nameof(span)} where {nameof(select)} is less than 0"); |
| | | 1682 | | } |
| | 5525 | 1683 | | max = Math.Max(max, temp); |
| | 5525 | 1684 | | } |
| | 31 | 1685 | | Span<T> sortingSpan = new T[span.Length]; |
| | 264 | 1686 | | for (uint divisor = 1; max / divisor > 0; divisor *= 10) |
| | 101 | 1687 | | { |
| | 101 | 1688 | | SortCounting<T, SortRadixSelect<T, TSelect>>(span, new() { Select = select, Divisor = divisor }, sortingSpan, max) |
| | 101 | 1689 | | } |
| | 35 | 1690 | | } |
| | | 1691 | | |
| | | 1692 | | internal struct SortRadixSelect<T, TSelect> : IFunc<T, uint> |
| | | 1693 | | where TSelect : struct, IFunc<T, uint> |
| | | 1694 | | { |
| | | 1695 | | internal TSelect Select; |
| | | 1696 | | internal uint Divisor; |
| | | 1697 | | |
| | 137886 | 1698 | | public uint Invoke(T a) => Select.Invoke(a) / Divisor; |
| | | 1699 | | } |
| | | 1700 | | |
| | | 1701 | | #endregion |
| | | 1702 | | |
| | | 1703 | | #region SortPidgeonHole |
| | | 1704 | | |
| | | 1705 | | /// <inheritdoc cref="SortPidgeonHole{TGet, TSet}(int, int, TGet, TSet)"/> |
| | | 1706 | | public static void SortPidgeonHole(int start, int end, Func<int, int> get, Action<int, int> set) |
| | 83 | 1707 | | { |
| | 83 | 1708 | | if (get is null) throw new ArgumentNullException(nameof(get)); |
| | 83 | 1709 | | if (set is null) throw new ArgumentNullException(nameof(set)); |
| | 83 | 1710 | | SortPidgeonHole<SFunc<int, int>, SAction<int, int>>(start, end, get, set); |
| | 83 | 1711 | | } |
| | | 1712 | | |
| | | 1713 | | /// <summary> |
| | | 1714 | | /// Sorts values using the pidgeon hole sort algorithm. |
| | | 1715 | | /// </summary> |
| | | 1716 | | /// <typeparam name="TGet">The type of get function.</typeparam> |
| | | 1717 | | /// <typeparam name="TSet">The type of set function.</typeparam> |
| | | 1718 | | /// <param name="start">The starting index of the sort.</param> |
| | | 1719 | | /// <param name="end">The ending index of the sort.</param> |
| | | 1720 | | /// <param name="get">The get function.</param> |
| | | 1721 | | /// <param name="set">The set function.</param> |
| | | 1722 | | public static void SortPidgeonHole<TGet, TSet>(int start, int end, TGet get = default, TSet set = default) |
| | | 1723 | | where TGet : struct, IFunc<int, int> |
| | | 1724 | | where TSet : struct, IAction<int, int> |
| | 83 | 1725 | | { |
| | 83 | 1726 | | if (end - start + 1 < 2) |
| | 10 | 1727 | | { |
| | 10 | 1728 | | return; |
| | | 1729 | | } |
| | 73 | 1730 | | int min = int.MaxValue; |
| | 73 | 1731 | | int max = int.MinValue; |
| | 24798 | 1732 | | for (int i = start; i <= end; i++) |
| | 12326 | 1733 | | { |
| | 12326 | 1734 | | int temp = get.Invoke(i); |
| | 12326 | 1735 | | if (i < 0) |
| | 0 | 1736 | | { |
| | 0 | 1737 | | throw new ArgumentException(message: $"a value exists in the sequence that is less than 0"); |
| | | 1738 | | } |
| | 12326 | 1739 | | max = Math.Max(max, temp); |
| | 12326 | 1740 | | min = Math.Min(min, temp); |
| | 12326 | 1741 | | } |
| | 73 | 1742 | | if (min < int.MinValue / 2 && max > -(int.MinValue / 2)) |
| | 0 | 1743 | | { |
| | 0 | 1744 | | throw new OverflowException($"the range of values in the sequence exceends the range of the int data type"); |
| | | 1745 | | } |
| | 73 | 1746 | | Span<int> holes = new int[max - min + 1]; |
| | 24798 | 1747 | | for (int i = start; i <= end; i++) |
| | 12326 | 1748 | | { |
| | 12326 | 1749 | | holes[get.Invoke(i) - min]++; |
| | 12326 | 1750 | | } |
| | 7132561 | 1751 | | for (int hole = 0, i = start; hole < holes.Length; hole++) |
| | 3566171 | 1752 | | { |
| | 7156994 | 1753 | | for (int j = 0; j < holes[hole]; j++) |
| | 12326 | 1754 | | { |
| | 12326 | 1755 | | set.Invoke(i++, hole + min); |
| | 12326 | 1756 | | } |
| | 3566171 | 1757 | | } |
| | 83 | 1758 | | } |
| | | 1759 | | |
| | | 1760 | | /// <summary> |
| | | 1761 | | /// Sorts values using the pidgeon hole sort algorithm. |
| | | 1762 | | /// </summary> |
| | | 1763 | | /// <param name="span">The span to be sorted.</param> |
| | | 1764 | | public static void SortPidgeonHole(Span<int> span) |
| | 83 | 1765 | | { |
| | 83 | 1766 | | if (span.Length < 2) |
| | 10 | 1767 | | { |
| | 10 | 1768 | | return; |
| | | 1769 | | } |
| | 73 | 1770 | | int min = int.MaxValue; |
| | 73 | 1771 | | int max = int.MinValue; |
| | 24871 | 1772 | | foreach (int i in span) |
| | 12326 | 1773 | | { |
| | 12326 | 1774 | | max = Math.Max(max, i); |
| | 12326 | 1775 | | min = Math.Min(min, i); |
| | 12326 | 1776 | | } |
| | 73 | 1777 | | if (min < int.MinValue / 2 && max > -(int.MinValue / 2)) |
| | 0 | 1778 | | { |
| | 0 | 1779 | | throw new OverflowException($"the range of values in {nameof(span)} exceends the range of the int data type"); |
| | | 1780 | | } |
| | 73 | 1781 | | Span<int> holes = new int[max - min + 1]; |
| | 24871 | 1782 | | foreach (int i in span) |
| | 12326 | 1783 | | { |
| | 12326 | 1784 | | holes[i - min]++; |
| | 12326 | 1785 | | } |
| | 7132561 | 1786 | | for (int hole = 0, i = 0; hole < holes.Length; hole++) |
| | 3566171 | 1787 | | { |
| | 7156994 | 1788 | | for (int j = 0; j < holes[hole]; j++) |
| | 12326 | 1789 | | { |
| | 12326 | 1790 | | span[i++] = hole + min; |
| | 12326 | 1791 | | } |
| | 3566171 | 1792 | | } |
| | 83 | 1793 | | } |
| | | 1794 | | |
| | | 1795 | | #endregion |
| | | 1796 | | |
| | | 1797 | | #region IntroSort |
| | | 1798 | | |
| | | 1799 | | /// <summary> |
| | | 1800 | | /// Sorts values using the introspective sort algorithm.<br/> |
| | | 1801 | | /// Runtime: Ω(n*ln(n)), ε(n*ln(n)), O(n*ln(n))<br/> |
| | | 1802 | | /// Memory: Θ(n)<br/> |
| | | 1803 | | /// Stable: False |
| | | 1804 | | /// </summary> |
| | | 1805 | | /// <inheritdoc cref="XML_Sort"/> |
| | | 1806 | | /// <citation> |
| | | 1807 | | /// The code for introspective sort was forked from the dotnet/runtime repo. Here is their license: |
| | | 1808 | | /// https://github.com/dotnet/runtime/blob/358ee3c9f61d8c11f7cac067307db1b2d6690f3c/src/libraries/System.Private.CoreL |
| | | 1809 | | /// |
| | | 1810 | | /// The MIT License (MIT) |
| | | 1811 | | /// |
| | | 1812 | | /// Copyright(c) .NET Foundation and Contributors |
| | | 1813 | | /// |
| | | 1814 | | /// All rights reserved. |
| | | 1815 | | /// |
| | | 1816 | | /// Permission is hereby granted, free of charge, to any person obtaining a copy |
| | | 1817 | | /// of this software and associated documentation files(the "Software"), to deal |
| | | 1818 | | /// in the Software without restriction, including without limitation the rights |
| | | 1819 | | /// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell |
| | | 1820 | | /// copies of the Software, and to permit persons to whom the Software is |
| | | 1821 | | /// furnished to do so, subject to the following conditions: |
| | | 1822 | | /// |
| | | 1823 | | /// The above copyright notice and this permission notice shall be included in all |
| | | 1824 | | /// copies or substantial portions of the Software. |
| | | 1825 | | /// |
| | | 1826 | | /// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
| | | 1827 | | /// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
| | | 1828 | | /// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE |
| | | 1829 | | /// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER |
| | | 1830 | | /// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, |
| | | 1831 | | /// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE |
| | | 1832 | | /// SOFTWARE. |
| | | 1833 | | /// </citation> |
| | | 1834 | | [Obsolete(NotIntended, true)] |
| | 1 | 1835 | | public static void XML_SortIntro() => throw new DocumentationMethodException(); |
| | | 1836 | | |
| | | 1837 | | internal const int IntrosortSizeThreshold = 16; |
| | | 1838 | | |
| | | 1839 | | /// <inheritdoc cref="XML_SortIntro"/> |
| | | 1840 | | public static void SortIntro<T>(int start, int end, Func<int, T> get, Action<int, T> set, Func<T, T, CompareResult>? c |
| | 83 | 1841 | | SortIntro<T, SFunc<int, T>, SAction<int, T>, SFunc<T, T, CompareResult>>(start, end, get, set, compare ?? Compare); |
| | | 1842 | | |
| | | 1843 | | /// <inheritdoc cref="XML_SortIntro"/> |
| | | 1844 | | public static void SortIntro<T, TGet, TSet, TCompare>(int start, int end, TGet get = default, TSet set = default, TCom |
| | | 1845 | | where TCompare : struct, IFunc<T, T, CompareResult> |
| | | 1846 | | where TGet : struct, IFunc<int, T> |
| | | 1847 | | where TSet : struct, IAction<int, T> |
| | 83 | 1848 | | { |
| | 83 | 1849 | | if (end - start > 0) |
| | 73 | 1850 | | { |
| | 73 | 1851 | | SortIntro<T, TGet, TSet, TCompare>(start, end, 2 * (System.Numerics.BitOperations.Log2((uint)(end - start)) + 1), |
| | 73 | 1852 | | } |
| | 83 | 1853 | | } |
| | | 1854 | | |
| | | 1855 | | internal static void SortIntro<T, TGet, TSet, TCompare>(int lo, int hi, int depthLimit, TGet get = default, TSet set = |
| | | 1856 | | where TCompare : struct, IFunc<T, T, CompareResult> |
| | | 1857 | | where TGet : struct, IFunc<int, T> |
| | | 1858 | | where TSet : struct, IAction<int, T> |
| | 1170 | 1859 | | { |
| | 2267 | 1860 | | while (hi > lo) |
| | 2255 | 1861 | | { |
| | 2255 | 1862 | | int partitionSize = hi - lo + 1; |
| | 2255 | 1863 | | if (partitionSize <= IntrosortSizeThreshold) |
| | 1158 | 1864 | | { |
| | 1158 | 1865 | | if (partitionSize is 2) |
| | 48 | 1866 | | { |
| | 79 | 1867 | | if (compare.Invoke(get.Invoke(lo), get.Invoke(hi)) is Greater) Swap<T, TGet, TSet>(lo, hi, get, set); |
| | 48 | 1868 | | return; |
| | | 1869 | | } |
| | | 1870 | | |
| | 1110 | 1871 | | if (partitionSize is 3) |
| | 45 | 1872 | | { |
| | 67 | 1873 | | if (compare.Invoke(get.Invoke(lo), get.Invoke(hi - 1)) is Greater) Swap<T, TGet, TSet>(lo, hi - 1, get, set); |
| | 57 | 1874 | | if (compare.Invoke(get.Invoke(lo), get.Invoke(hi)) is Greater) Swap<T, TGet, TSet>(lo, hi, get, set); |
| | 72 | 1875 | | if (compare.Invoke(get.Invoke(hi - 1), get.Invoke(hi)) is Greater) Swap<T, TGet, TSet>(hi - 1, hi, get, set); |
| | 45 | 1876 | | return; |
| | | 1877 | | } |
| | 1065 | 1878 | | SortInsertion<T, TGet, TSet, TCompare>(lo, hi, get, set, compare); |
| | 1065 | 1879 | | return; |
| | | 1880 | | } |
| | 1097 | 1881 | | if (depthLimit is 0) |
| | 0 | 1882 | | { |
| | 0 | 1883 | | SortHeap<T, TGet, TSet, TCompare>(lo, hi, get, set, compare); |
| | 0 | 1884 | | return; |
| | | 1885 | | } |
| | 1097 | 1886 | | int p = PickPivotAndPartition<T, TGet, TSet, TCompare>(lo, hi, get, set, compare); |
| | 1097 | 1887 | | SortIntro<T, TGet, TSet, TCompare>(p + 1, hi, --depthLimit, get, set, compare); |
| | 1097 | 1888 | | hi = p - 1; |
| | 1097 | 1889 | | } |
| | 1170 | 1890 | | } |
| | | 1891 | | |
| | | 1892 | | internal static int PickPivotAndPartition<T, TGet, TSet, TCompare>(int lo, int hi, TGet get = default, TSet set = defa |
| | | 1893 | | where TCompare : struct, IFunc<T, T, CompareResult> |
| | | 1894 | | where TGet : struct, IFunc<int, T> |
| | | 1895 | | where TSet : struct, IAction<int, T> |
| | 1097 | 1896 | | { |
| | 1097 | 1897 | | int mid = lo + (hi - lo) / 2; |
| | 1642 | 1898 | | if (compare.Invoke(get.Invoke(lo), get.Invoke(mid)) is Greater) Swap<T, TGet, TSet>(lo, mid, get, set); |
| | 1496 | 1899 | | if (compare.Invoke(get.Invoke(lo), get.Invoke(hi)) is Greater) Swap<T, TGet, TSet>(lo, hi, get, set); |
| | 1842 | 1900 | | if (compare.Invoke(get.Invoke(mid), get.Invoke(hi)) is Greater) Swap<T, TGet, TSet>(mid, hi, get, set); |
| | 1097 | 1901 | | T pivot = get.Invoke(mid); |
| | 1097 | 1902 | | Swap<T, TGet, TSet>(mid, hi - 1, get, set); |
| | 1097 | 1903 | | int left = lo; |
| | 1097 | 1904 | | int right = hi - 1; |
| | 17482 | 1905 | | while (left < right) |
| | 17482 | 1906 | | { |
| | 40631 | 1907 | | while (compare.Invoke(get.Invoke(++left), pivot) is Less) |
| | 23149 | 1908 | | { |
| | | 1909 | | // spin |
| | 23149 | 1910 | | } |
| | 41453 | 1911 | | while (compare.Invoke(pivot, get.Invoke(--right)) is Less) |
| | 23971 | 1912 | | { |
| | | 1913 | | // spin |
| | 23971 | 1914 | | } |
| | 17482 | 1915 | | if (left >= right) |
| | 1097 | 1916 | | { |
| | 1097 | 1917 | | break; |
| | | 1918 | | } |
| | 16385 | 1919 | | Swap<T, TGet, TSet>(left, right, get, set); |
| | 16385 | 1920 | | } |
| | 1097 | 1921 | | if (left != hi - 1) |
| | 1090 | 1922 | | { |
| | 1090 | 1923 | | Swap<T, TGet, TSet>(left, hi - 1, get, set); |
| | 1090 | 1924 | | } |
| | 1097 | 1925 | | return left; |
| | 1097 | 1926 | | } |
| | | 1927 | | |
| | | 1928 | | /// <inheritdoc cref="XML_SortIntro"/> |
| | | 1929 | | public static void SortIntro<T>(Span<T> span, Func<T, T, CompareResult>? compare = null) => |
| | 83 | 1930 | | SortIntro<T, SFunc<T, T, CompareResult>>(span, compare ?? Compare); |
| | | 1931 | | |
| | | 1932 | | /// <inheritdoc cref="XML_SortIntro"/> |
| | | 1933 | | public static void SortIntro<T, TCompare>(Span<T> span, TCompare compare = default) |
| | | 1934 | | where TCompare : struct, IFunc<T, T, CompareResult> |
| | 83 | 1935 | | { |
| | 83 | 1936 | | if (span.Length > 1) |
| | 73 | 1937 | | { |
| | 73 | 1938 | | SortIntro(span, 2 * (System.Numerics.BitOperations.Log2((uint)span.Length) + 1), compare); |
| | 73 | 1939 | | } |
| | 83 | 1940 | | } |
| | | 1941 | | |
| | | 1942 | | internal static void SortIntro<T, TCompare>(Span<T> span, int depthLimit, TCompare compare = default) |
| | | 1943 | | where TCompare : struct, IFunc<T, T, CompareResult> |
| | 1170 | 1944 | | { |
| | 1170 | 1945 | | if (span.Length > 1) |
| | 1163 | 1946 | | { |
| | 1163 | 1947 | | int lo = 0; |
| | 1163 | 1948 | | int hi = span.Length - 1; |
| | 2260 | 1949 | | while (hi > lo) |
| | 2255 | 1950 | | { |
| | 2255 | 1951 | | int partitionSize = hi - lo + 1; |
| | 2255 | 1952 | | if (partitionSize <= IntrosortSizeThreshold) |
| | 1158 | 1953 | | { |
| | 1158 | 1954 | | if (partitionSize is 2) |
| | 48 | 1955 | | { |
| | 79 | 1956 | | if (compare.Invoke(span[lo], span[hi]) is Greater) Swap(ref span[lo], ref span[hi]); |
| | 48 | 1957 | | return; |
| | | 1958 | | } |
| | 1110 | 1959 | | if (partitionSize is 3) |
| | 45 | 1960 | | { |
| | 67 | 1961 | | if (compare.Invoke(span[lo], span[hi - 1]) is Greater) Swap(ref span[lo], ref span[hi - 1]); |
| | 57 | 1962 | | if (compare.Invoke(span[lo], span[hi]) is Greater) Swap(ref span[lo], ref span[hi]); |
| | 72 | 1963 | | if (compare.Invoke(span[hi - 1], span[hi]) is Greater) Swap(ref span[hi - 1], ref span[hi]); |
| | 45 | 1964 | | return; |
| | | 1965 | | } |
| | 1065 | 1966 | | SortInsertion(span[lo..(hi + 1)], compare); |
| | 1065 | 1967 | | return; |
| | | 1968 | | } |
| | 1097 | 1969 | | if (depthLimit is 0) |
| | 0 | 1970 | | { |
| | 0 | 1971 | | SortHeap(span[lo..(hi + 1)], compare); |
| | 0 | 1972 | | return; |
| | | 1973 | | } |
| | 1097 | 1974 | | int p = PickPivotAndPartition(span, lo, hi, compare); |
| | 1097 | 1975 | | SortIntro(span[(p + 1)..(hi + 1)], --depthLimit, compare); |
| | 1097 | 1976 | | hi = p - 1; |
| | 1097 | 1977 | | } |
| | 5 | 1978 | | } |
| | 1170 | 1979 | | } |
| | | 1980 | | |
| | | 1981 | | internal static int PickPivotAndPartition<T, TCompare>(Span<T> span, int lo, int hi, TCompare compare = default) |
| | | 1982 | | where TCompare : struct, IFunc<T, T, CompareResult> |
| | 1097 | 1983 | | { |
| | 1097 | 1984 | | int mid = lo + (hi - lo) / 2; |
| | 1642 | 1985 | | if (compare.Invoke(span[lo], span[mid]) is Greater) Swap(ref span[lo], ref span[mid]); |
| | 1496 | 1986 | | if (compare.Invoke(span[lo], span[hi]) is Greater) Swap(ref span[lo], ref span[hi]); |
| | 1842 | 1987 | | if (compare.Invoke(span[mid], span[hi]) is Greater) Swap(ref span[mid], ref span[hi]); |
| | 1097 | 1988 | | T pivot = span[mid]; |
| | 1097 | 1989 | | Swap(ref span[mid], ref span[hi - 1]); |
| | 1097 | 1990 | | int left = lo; |
| | 1097 | 1991 | | int right = hi - 1; |
| | 17482 | 1992 | | while (left < right) |
| | 17482 | 1993 | | { |
| | 40631 | 1994 | | while (compare.Invoke(span[++left], pivot) is Less) |
| | 23149 | 1995 | | { |
| | | 1996 | | // spin |
| | 23149 | 1997 | | } |
| | 41453 | 1998 | | while (compare.Invoke(pivot, span[--right]) is Less) |
| | 23971 | 1999 | | { |
| | | 2000 | | // spin |
| | 23971 | 2001 | | } |
| | 17482 | 2002 | | if (left >= right) |
| | 1097 | 2003 | | { |
| | 1097 | 2004 | | break; |
| | | 2005 | | } |
| | 16385 | 2006 | | Swap(ref span[left], ref span[right]); |
| | 16385 | 2007 | | } |
| | 1097 | 2008 | | if (left != hi - 1) |
| | 1090 | 2009 | | { |
| | 1090 | 2010 | | Swap(ref span[left], ref span[hi - 1]); |
| | 1090 | 2011 | | } |
| | 1097 | 2012 | | return left; |
| | 1097 | 2013 | | } |
| | | 2014 | | |
| | | 2015 | | #endregion |
| | | 2016 | | } |