Sorting algorithms/Quicksort: Difference between revisions
m
Guarded against Arithmetic Overflow.
(Opted for linear interpolation, to remove the dependency on Math.Random, when obtaining samples for estimation of a median by pivot(). The median is now returned and passed via locals, rather than a property.) |
m (Guarded against Arithmetic Overflow.) |
||
Line 1,849:
}
private static Int32 sampleSize(Int32 length, Int32 max = SAMPLES_MAX) {
var logLen = (Int32)Math.Log10(length);
▲ // An odd sample size is chosen based on the log of the interval size.
▲ var samples = Math.Min(2 * logLen + 1, SAMPLES_MAX);
return Math.Min(samples, length);
}
/// <summary>Estimate the median value of entries[Left:Right]</summary>
/// <remarks>The sample median is used as an estimate the true median.</remarks>
private T pivot(T[] entries) {
var length = Right + 1 - Left;
var samples = sampleSize(length);
// Sample Linearly:
for (var sample = 0; sample < samples; sample++) {
//
var index = (Int64)length * sample / samples + Left;
Samples[sample] = entries[index];
}
InsertionSort<T>.Sort(Samples, 0, samples - 1);
var middle = samples / 2;
| |||