Interface IPivotSelectionStrategy

An algorithm to select the pivot from the provided window of a list, to be used by a IThreeWayPartitionStrategy, to partition the window into three segments.

Namespace: MoreStructures.Lists.Sorting.QuickSort
Assembly: MoreStructures.dll
Syntax
public interface IPivotSelectionStrategy
Remarks

COMPLEXITY
- For the overall quicksort algorithm to have the expected complexity, pivot selection should not exceed the linear Time Complexity.
- While a linear time algorithm would ensure best pivot selection and list window partition (e.g. picking the actual median of all values), and while it would still keep overall quicksort runtime to be linearithmic, the multiplicative factor of n * log(n) would be much higher than a quicksort based on a O(1) pivot selection, such as a deterministic choice or a randomized one.
- So, even asymptotically, the advantages of having a smart, O(n), pivot selection would be overwhelmed by the negative impact of the pivot selection cost at every recursive call of the quicksort on a window.

Methods

| Improve this Doc View Source

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

Selects a pivot from the window of the provided list, defined by start and end indices.

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

The list, whose pivot has to be selected.
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.Int32

The index of the pivot in list.
Type Parameters
Name Description
T

The type of items in list.

Extension Methods