Class StartIndexPivotSelectionStrategy

A IPivotSelectionStrategy always picking the lowest index of the window.

Inheritance
System.Object
StartIndexPivotSelectionStrategy
Implements
Inherited Members
System.Object.Equals(System.Object)
System.Object.Equals(System.Object, System.Object)
System.Object.GetHashCode()
System.Object.GetType()
System.Object.MemberwiseClone()
System.Object.ReferenceEquals(System.Object, System.Object)
System.Object.ToString()
Namespace: MoreStructures.Lists.Sorting.QuickSort
Assembly: MoreStructures.dll
Syntax
public class StartIndexPivotSelectionStrategy : IPivotSelectionStrategy
Remarks

Time and Space Complexity are O(1).
While one of the simplest way of selecting a pivot, when used in a IThreeWayPartitionStrategy of a RecursiveQuickSort instance, it makes quicksort run in quadratic time on pathological input configurations, and in particular when the input window is already sorted in ascending order.
To avoid phatological scenarios with this IPivotSelectionStrategy, setup a IShuffleStrategy in the RecursiveQuickSort instance, different from IdentityShuffleStrategy.

Methods

| Improve this Doc View Source

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

Declaration
public int Select<T>(IList<T> list, IComparer<T> comparer, int start, int end)
Parameters
Type Name Description
IList<T> list
IComparer<T> comparer
System.Int32 start
System.Int32 end
Returns
Type Description
System.Int32
Type Parameters
Name Description
T
Remarks

This specific implementation always picks the start index.

Implements

Extension Methods