Sorting algorithms/Quicksort: Difference between revisions

← Older editNewer edit →
Content deleted Content added
Alextretyak (talk | contribs)
1,481 edits
Added 11l
CNHume (talk | contribs)
159 edits
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.
Line 1,784: Line 1,784:
#define Tripartite
#define Tripartite


namespace Sort {
namespace RosettaCode {
using System;
using System;
using System.Diagnostics;
using System.Diagnostics;


class QuickSort<T> where T : IComparable {
public class QuickSort<T> where T : IComparable {
#region Constants
#region Constants
private const Int32 INSERTION_LIMIT_DEFAULT = 12;
public const Int32 INSERTION_LIMIT_DEFAULT = 12;
private const Int32 SAMPLES_MAX = 19;
#endregion
#endregion


#region Properties
#region Properties
public Int32 InsertionLimit { get; set; }
public Int32 InsertionLimit { get; init; }
private Random Random { get; set; }
private T[] Samples { get; init; }
private T Median { get; set; }

private Int32 Left { get; set; }
private Int32 Left { get; set; }
private Int32 Right { get; set; }
private Int32 Right { get; set; }
Line 1,805: Line 1,804:


#region Constructors
#region Constructors
public QuickSort(Int32 insertionLimit, Random random) {
public QuickSort(Int32 insertionLimit = INSERTION_LIMIT_DEFAULT) {
this.InsertionLimit = insertionLimit;
this.InsertionLimit = insertionLimit;
this.Random = random;
this.Samples = new T[SAMPLES_MAX];
⚫
}

public QuickSort(Int32 insertionLimit)
: this(insertionLimit, new Random()) {
⚫
}

public QuickSort()
: this(INSERTION_LIMIT_DEFAULT) {
}
}
#endregion
#endregion
Line 1,834: Line 1,825:
Left = first;
Left = first;
Right = last;
Right = last;
pivot(entries);
var median = pivot(entries);
partition(entries);
partition(median, entries);
//[Note]Right < Left
//[Note]Right < Left


Line 1,858: Line 1,849:
}
}


private void pivot(T[] entries) {
private static Int32 sampleSize(Int32 length) {
⚫
var logLen = (Int32)Math.Log10(length);
//
//
// An odd sample size is chosen based on the log of the interval size.
// An odd sample size is chosen based on the log of the interval size.
Line 1,864: Line 1,856:
// an estimate of the true median.
// an estimate of the true median.
//
//
var samples = Math.Min(2 * logLen + 1, SAMPLES_MAX);
return Math.Min(samples, length);
⚫
}

/// <summary>Estimate the median value of entries[Left:Right]</summary>
private T pivot(T[] entries) {
var length = Right + 1 - Left;
var length = Right + 1 - Left;
var logLen = (Int32)Math.Log10(length);
var samples = sampleSize(length);
var pivotSamples = 2 * logLen + 1;
for (var sample = 0; sample < samples; sample++) {
⚫
// Sample Linearly:
⚫
var sampleSize = Math.Min(pivotSamples, length);
var last = Left + sampleSize - 1;
var index = length * sample / samples + Left;
⚫
Samples[sample] = entries[index];
⚫
// Sample without replacement
for (var first = Left; first <= last; first++) {
// Random sampling avoids pathological cases
var random = Random.Next(first, Right + 1);
Swap(entries, first, random);
}
}
⚫
InsertionSort<T>.Sort(Samples, 0, samples - 1);

var middle = samples / 2;
⚫
InsertionSort<T>.Sort(entries, Left, last);
Median = entries[Left + sampleSize / 2];
return Samples[middle];
}
}


private void partition(T[] entries) {
private void partition(T median, T[] entries) {
var first = Left;
var first = Left;
var last = Right;
var last = Right;
Line 1,888: Line 1,882:
#endif
#endif
while (true) {
while (true) {
//[Assert]There exists some index >= Left where entries[index] >= Median
//[Assert]There exists some index >= Left where entries[index] >= median
//[Assert]There exists some index <= Right where entries[index] <= Median
//[Assert]There exists some index <= Right where entries[index] <= median
// So, there is no need for Left or Right bound checks
// So, there is no need for Left or Right bound checks
while (Median.CompareTo(entries[Left]) > 0) Left++;
while (median.CompareTo(entries[Left]) > 0) Left++;
while (Median.CompareTo(entries[Right]) < 0) Right--;
while (median.CompareTo(entries[Right]) < 0) Right--;


//[Assert]entries[Right] <= Median <= entries[Left]
//[Assert]entries[Right] <= median <= entries[Left]
if (Right <= Left) break;
if (Right <= Left) break;


Swap(entries, Left, Right);
Swap(entries, Left, Right);
swapOut(entries);
swapOut(median, entries);
Left++;
Left++;
Right--;
Right--;
//[Assert]entries[first:Left - 1] <= Median <= entries[Right + 1:last]
//[Assert]entries[first:Left - 1] <= median <= entries[Right + 1:last]
}
}


Line 1,911: Line 1,905:
swapIn(entries, first, last);
swapIn(entries, first, last);


//[Assert]entries[first:Right] <= Median <= entries[Left:last]
//[Assert]entries[first:Right] <= median <= entries[Left:last]
//[Assert]entries[Right + 1:Left - 1] == Median when non-empty
//[Assert]entries[Right + 1:Left - 1] == median when non-empty
}
}
#endregion
#endregion
Line 1,918: Line 1,912:
#region Swap Methods
#region Swap Methods
[Conditional("Tripartite")]
[Conditional("Tripartite")]
private void swapOut(T[] entries) {
private void swapOut(T median, T[] entries) {
if (Median.CompareTo(entries[Left]) == 0) Swap(entries, LeftMedian++, Left);
if (median.CompareTo(entries[Left]) == 0) Swap(entries, LeftMedian++, Left);
if (Median.CompareTo(entries[Right]) == 0) Swap(entries, Right, RightMedian--);
if (median.CompareTo(entries[Right]) == 0) Swap(entries, Right, RightMedian--);
}
}


Line 1,930: Line 1,924:
}
}


public static void Swap(T[] entries, Int32 index1, Int32 index2) {
/// <summary>Swap entries at the left and right indicies.</summary>
⚫
public void Swap(T[] entries, Int32 left, Int32 right) {
if (index1 != index2) {
var entry = entries[index1];
Swap(ref entries[left], ref entries[right]);
⚫
}
entries[index1] = entries[index2];

⚫
entries[index2] = entry;
/// <summary>Swap two entities of type T.</summary>
⚫
}
public static void Swap(ref T e1, ref T e2) {
var e = e1;
e1 = e2;
⚫
e2 = e;
}
}
#endregion
#endregion
Line 1,943: Line 1,941:
static class InsertionSort<T> where T : IComparable {
static class InsertionSort<T> where T : IComparable {
public static void Sort(T[] entries, Int32 first, Int32 last) {
public static void Sort(T[] entries, Int32 first, Int32 last) {
for (var index = first + 1; index <= last; index++)
for (var next = first + 1; next <= last; next++)
insert(entries, first, index);
insert(entries, first, next);
}
}


/// <summary>Bubble next entry up to its sorted location, assuming entries[first:next - 1] are already sorted.</summary>
⚫
private static void insert(T[] entries, Int32 first, Int32 index) {
private static void insert(T[] entries, Int32 first, Int32 next) {
⚫
var entry = entries[index];
while (index > first && entries[index - 1].CompareTo(entry) > 0)
var entry = entries[next];
entries[index] = entries[--index];
while (next > first && entries[next - 1].CompareTo(entry) > 0)
entries[index] = entry;
entries[next] = entries[--next];
⚫
entries[next] = entry;
}
}
}
}
Retrieved from "https://rosettacode.org/wiki/Sorting_algorithms/Quicksort"