Sorting algorithms/Quicksort: Difference between revisions
Content deleted Content added
Added Bentley-McIlroy 3-way Partitioning |
|||
Line 1,093:
=={{header|C sharp|C#}}==
Note that Array.Sort and ArrayList.Sort both use an unstable implementation of the quicksort algorithm.
<lang csharp>#define Tripartite // Improve equal key performance with minimal overhead
<lang csharp>namespace Sort {▼
using System;
Line 1,107 ⟶ 1,109:
#region Constructors
public QuickSort()▼
: this(insertionLimitDefault, new Random()) {▼
}▼
public QuickSort(Int32 insertionLimit, Random random) {
InsertionLimit = insertionLimit;
Random = random;
▲ }
▲ public QuickSort()
▲ : this(insertionLimitDefault, new Random()) {
}
#endregion
Line 1,157 ⟶ 1,159:
private static void partition(T[] entries, T median, ref Int32 left, ref Int32 right) {
var leftMedian = first;
var rightMedian = last;
//[Assert]There exists some index >= left where entries[index] >= median
//[Assert]There exists some index <= right where entries[index] <= median
Line 1,168 ⟶ 1,172:
//[Assert]entries[right] <= median <= entries[left]
if (
Swap(entries, left, right);
#if Tripartite
// Bentley-McIlroy 3-way Partitioning: Put median entries aside
if (median.CompareTo(entries[left]) == 0) Swap(entries, leftMedian++, left);
if (median.CompareTo(entries[right]) == 0) Swap(entries, right, rightMedian--);
#endif
left++;
right--;
//[Assert]entries[first:left - 1] <= median <= entries[right + 1:last]
}
if (left == right) {
left++;
right--;
}
//[Assert]right < left
#if Tripartite
// entries[first:right] <= median <= entries[left:last]▼
//
for (var prefix = first; prefix < leftMedian;)
Swap(entries, prefix++, right--);
for (var suffix = last; rightMedian < suffix;)
Swap(entries, left++, suffix--);
#endif
//[Assert]entries[right + 1:left - 1] == median when non-empty
}
| |||