| | | 1 | | using MoreStructures.Utilities; |
| | | 2 | | |
| | | 3 | | namespace MoreStructures.Lists.Sorting.QuickSort; |
| | | 4 | | |
| | | 5 | | /// <summary> |
| | | 6 | | /// A <see cref="IPivotSelectionStrategy"/> always picking the index of the window in the middle. |
| | | 7 | | /// </summary> |
| | | 8 | | /// <remarks> |
| | | 9 | | /// Time and Space Complexity are O(1). |
| | | 10 | | /// <br/> |
| | | 11 | | /// Like for <see cref="StartIndexPivotSelectionStrategy"/> and <see cref="EndIndexPivotSelectionStrategy"/>, it makes |
| | | 12 | | /// quicksort run in quadratic time on pathological input configurations. |
| | | 13 | | /// <br/> |
| | | 14 | | /// However, unlike <see cref="StartIndexPivotSelectionStrategy"/> and <see cref="EndIndexPivotSelectionStrategy"/>, |
| | | 15 | | /// the pathological scenarios are much more unlikely to happen in the wild, and usually have to be manually crafted. |
| | | 16 | | /// <br/> |
| | | 17 | | /// To further reduce the possibility of phatological scenarios, and make sure that the resulting quicksort doesn't |
| | | 18 | | /// behave consistently bad on the same input, setup a <see cref="IShuffleStrategy"/> in the |
| | | 19 | | /// <see cref="RecursiveQuickSort"/> instance, different from <see cref="IdentityShuffleStrategy"/>. |
| | | 20 | | /// </remarks> |
| | | 21 | | public class MiddleIndexPivotSelectionStrategy : IPivotSelectionStrategy |
| | | 22 | | { |
| | | 23 | | /// <inheritdoc path="//*[not(self::remarks)]"/> |
| | | 24 | | /// <remarks> |
| | | 25 | | /// This specific implementation always picks the <paramref name="end"/> index. |
| | | 26 | | /// </remarks> |
| | | 27 | | public int Select<T>(IList<T> list, IComparer<T> comparer, int start, int end) => |
| | 546 | 28 | | (start, end).Middle(); |
| | | 29 | | } |