| | | 1 | | namespace MoreStructures.Lists.Sorting.QuickSort; |
| | | 2 | | |
| | | 3 | | /// <summary> |
| | | 4 | | /// A <see cref="IPivotSelectionStrategy"/> always picking the lowest index of the window. |
| | | 5 | | /// </summary> |
| | | 6 | | /// <remarks> |
| | | 7 | | /// Time and Space Complexity are O(1). |
| | | 8 | | /// <br/> |
| | | 9 | | /// While one of the simplest way of selecting a pivot, when used in a <see cref="IThreeWayPartitionStrategy"/> of a |
| | | 10 | | /// <see cref="RecursiveQuickSort"/> instance, it makes quicksort run in quadratic time on pathological input |
| | | 11 | | /// configurations, and in particular when the input window is already sorted in ascending order. |
| | | 12 | | /// <br/> |
| | | 13 | | /// To avoid phatological scenarios with this <see cref="IPivotSelectionStrategy"/>, setup a |
| | | 14 | | /// <see cref="IShuffleStrategy"/> in the <see cref="RecursiveQuickSort"/> instance, different from |
| | | 15 | | /// <see cref="IdentityShuffleStrategy"/>. |
| | | 16 | | /// </remarks> |
| | | 17 | | public class StartIndexPivotSelectionStrategy : IPivotSelectionStrategy |
| | | 18 | | { |
| | | 19 | | /// <inheritdoc path="//*[not(self::remarks)]"/> |
| | | 20 | | /// <remarks> |
| | | 21 | | /// This specific implementation always picks the <paramref name="start"/> index. |
| | | 22 | | /// </remarks> |
| | 559 | 23 | | public int Select<T>(IList<T> list, IComparer<T> comparer, int start, int end) => start; |
| | | 24 | | } |