Interface IThreeWayPartitionStrategy

An algorithm partitioning the specified window of the provided list "3-way", i.e. into three adjacent segments:

  • the first, named left segment, containing all items smaller or equal than the pivot,
  • the second, named middle segment, containing all items equals to the pivot,
  • and the third, named right segment, containing all items bigger or equal than the pivot.
Namespace: MoreStructures.Lists.Sorting.QuickSort
Assembly: MoreStructures.dll
Syntax
public interface IThreeWayPartitionStrategy
Remarks

The definition is "loose" enough to allow for overlapping: values equal to the pivot can be in either of the three segments.
Some partition strategies may be stricter, and only place pivot values in the middle segments.
Others may not do that, and just have an empty middle segments and pivot values split, evenly or not, in left and right segments.
A 3-way partition strategy returning an empty middle segment is actually a 2-way partition strategy.
This interface provide generality for partitioning schemes. However, the specific quicksort implementation may or may not support 2-way or 3-way partitions, empty partitions, etc.

Methods

| Improve this Doc View Source

Partition<T>(IList<T>, IComparer<T>, Int32, Int32)

Partition the window of the provided list, delimited by the indexes start and end included, into three segments, of items non-bigger, equal and non-smaller than the pivot, respectively.

Declaration
(int, int) Partition<T>(IList<T> list, IComparer<T> comparer, int start, int end)
Parameters
Type Name Description
IList<T> list

The list whose window has to be partitioned.
IComparer<T> comparer

A for the items of list.
System.Int32 start

The left index of the window of list, included.
System.Int32 end

The right index of the window of list, included.
Returns
Type Description
System.ValueTuple<System.Int32, System.Int32>

Two indices: the left and right indices of the middle segment, included.
If left and right index are equal, the middle segment is composed of a single value.
If the right index is strictly smaller than the left index, the middle segment is empty.
Type Parameters
Name Description
T

The type of items in list.
Remarks

If Partition(L, C, s, e) is equal to (l, r), the three partitions are identified by:

  • [s, l - 1]
  • [l, r]
  • [r + 1, e]
    where each of the partitions is empty if its left index is greater than its right index.

Extension Methods