Sorting algorithms/Quicksort: Difference between revisions
→{{header|C sharp|C#}}
m ({{out}}) |
|||
Line 773:
}</lang>
=={{header|C sharp|C#}}==
Note that
<lang csharp>
using System
static class QuickSort<T> where T : IComparable {
#region Constants
private const Int32 insertionLimitDefault = 32;
private const Int32 pivotSamples = 5;
#endregion
#region Properties
public static Int32 InsertionLimit { get; set; }
private static Random Random { get; set; }
#endregion
#region Constructors
static QuickSort() {
InsertionLimit = insertionLimitDefault;
Random = new Random();
}
#endregion
#region Sort Methods
public static void Sort(T[] entries) {
Sort(entries, 0, entries.Length - 1);
}
public static void Sort(T[] entries, Int32 first, Int32 last) {
var length = last + 1 - first;
while (length > 1) { // Tail recurse over longer partition
if (length < InsertionLimit) {
InsertionSort<T>.Sort(entries, first, last);
return;
}
var left = first;
var right =
partition(entries, median, ref left, ref
var leftLength = right
var rightLength = last
if (leftLength < rightLength) {
first =
length =
}
else
Sort(entries, left,
length =
}
private static T pivot(T[] entries, Int32 first, Int32 last) {
var length = last + 1
var sampleSize = Math.Min(pivotSamples, length);
var right = first + sampleSize - 1;
for (var left = first; left <= right; left++) {
// Random sampling avoids pathological cases
var random = Random.Next(left, last + 1);
// Sample without replacement
if (left != random)
Swap(entries, left, random);
}
InsertionSort<T>.Sort(entries, first, right);
return entries[first + sampleSize / 2];
}
private static void partition(T[] entries, T pivot, ref Int32 left, ref Int32 right) {
while (left <= right) {
while (pivot.CompareTo(entries[left]) > 0)
left++; // pivot follows entry
while (pivot.CompareTo(entries[right]) < 0)
right--; // pivot precedes entry
if (left < right) // Move entries to their correct partition
Swap(entries, left++, right--);
else if (left == right) { // No swap needed
left++;
right--;
}
}
}
internal static void Swap(T[] entries, Int32 index1, Int32 index2) {
var entry = entries[index1];
entries[index1] = entries[index2];
entries[index2] = entry;
}
#endregion
#region Insertion Sort
static class InsertionSort<T> where T : IComparable {
public static void Sort(T[] entries, Int32 first, Int32 last) {
for (var i = first + 1; i <= last; i++) {
var insert = entries[i];
var j = i;
while (j > first && entries[j - 1].CompareTo(insert) > 0)
entries[j] = entries[--j];
entries[j] = insert;
}
}
}
#endregion
}
}</lang>
| |||