< Summary

Information
Class: MoreStructures.Lists.Sorting.QuickSort.RecursiveQuickSort
Assembly: MoreStructures
File(s): /home/runner/work/MoreStructures/MoreStructures/MoreStructures/Lists/Sorting/QuickSort/RecursiveQuickSort.cs
Line coverage
100%
Covered lines: 18
Uncovered lines: 0
Coverable lines: 18
Total lines: 136
Line coverage: 100%
Branch coverage
100%
Covered branches: 2
Total branches: 2
Branch coverage: 100%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
get_ShuffleStrategy()100%1100%
get_PartitionStrategy()100%1100%
.ctor(...)100%1100%
Sort(...)100%1100%
Sort(...)100%1100%
RecursiveSort(...)100%2100%

File(s)

/home/runner/work/MoreStructures/MoreStructures/MoreStructures/Lists/Sorting/QuickSort/RecursiveQuickSort.cs

#LineLine coverage
 1namespace MoreStructures.Lists.Sorting.QuickSort;
 2
 3/// <summary>
 4/// An <see cref="IInputMutatingSort"/> implementation based on the quicksort algorithm.
 5/// </summary>
 6/// <remarks>
 7///     <para id="advantages">
 8///     ADVANTAGES AND DISADVANTAGES
 9///     <br/>
 10///     - Like <see cref="MergeSort"/>, it belongs to the category of linearithmic comparison-based sorting algorithm
 11///       (when setup correctly, see the complexity analysis section below).
 12///       <br/>
 13///     - Compared to <see cref="MergeSort"/>, it is <b>in-place</b>, having O(1) Space Complexity.
 14///       <br/>
 15///     - However, it is <b>not stable</b> and it's <b>not as easy parallelizable</b> as <see cref="MergeSort"/>.
 16///       <br/>
 17///     - While it is not optimal in the exact number of comparisons (it does in average 39% more comparisons than
 18///       <see cref="MergeSort"/>, which is optimal on the number of comparisons), it does way less swapping and moving
 19///       operations, resulting in a visibly better performance, especially when cost of moving items is high.
 20///       <br/>
 21///     - For that reason is tipically the <b>algorithm of choice when sorting primitive values or value types</b>,
 22///       such as struct instances, where cost of comparison is low and cost of swapping can be high, depending on the
 23///       size of the struct.
 24///       <br/>
 25///     - When sorting reference types, such as class instances, <see cref="MergeSort"/> is sometimes preferred, since
 26///       swapping items in the list means swapping their references, which are of fixed and small size, and instead
 27///       the cost of comparison can be quite high, depending on the <see cref="IComparable{T}"/> or on the
 28///       <see cref="IComparer{T}"/> implementation used.
 29///       <br/>
 30///     - Compared to most other comparison-based algorithms, a disadvantage of quicksort is that, for it to have
 31///       consistently good performances, it has to be randomized. In such setup, it is <b>not deterministic</b>.
 32///     </para>
 33///     <para id="algorithm">
 34///     ALGORITHM
 35///     <br/>
 36///     - First, it shuffles the input to sort, by using the <see cref="IShuffleStrategy"/> provided in the
 37///       constructor.
 38///       <br/>
 39///     - Then, it partitions the shuffled input into three segments: left, middle and right.
 40///       <br/>
 41///     - Partitioning is done via the <see cref="IThreeWayPartitionStrategy"/> provided in the constructor. The way in
 42///       which partitions are done, and in particular whether pivot values only appear in the middle segment, only in
 43///       left and/or right segments or in all three segments, depends on the specific strategy used.
 44///       <br/>
 45///     - In either case, the left contains items non-bigger than the pivot (possibly including pivot values), the
 46///       middle items equal to the pivot (and no other values) and the right items non-smaller than the pivot
 47///       (possibly including pivot values).
 48///       <br/>
 49///     - Items in the middle segments have already been placed by the algorithm in their final position. Therefore,
 50///       the middle segment doesn't have to be sorted any further. Left and rights segments, instead, are not sorted.
 51///       <br/>
 52///     - So the algorithm calls recursively the quicksort on the left and right segments, to sort them.
 53///       <br/>
 54///     - When the recursion terminates, the entire list is sorted.
 55///     </para>
 56///     <para id="complexity">
 57///     COMPLEXITY
 58///     <br/>
 59///     - Worst-case Time Complexity is O(n^2) and Space Complexity is O(1), since sorting happens entirely in place,
 60///       by repeated swapping.
 61///       <br/>
 62///     - Expected Time Complexity heavily depends on the choice of <see cref="IShuffleStrategy"/> and
 63///       <see cref="IThreeWayPartitionStrategy"/>, which in turns depends on the choice of
 64///       <see cref="IPivotSelectionStrategy"/>.
 65///       <br/>
 66///     - For example, using <see cref="IdentityShuffleStrategy"/> and <see cref="StartIndexPivotSelectionStrategy"/>
 67///       with inputs already sorted in ascending order, makes quicksort selects the worst pivot at every iteration,
 68///       partitioning each window of the input list in the most unbalanced way (left segment empty and right segment
 69///       containing all items but the pivot), and making quicksort behaving quadratically.
 70///       <br/>
 71///     - The same happens when using <see cref="IdentityShuffleStrategy"/> and
 72///       <see cref="EndIndexPivotSelectionStrategy"/>, with inputs already sorted in descending order.
 73///       <br/>
 74///     - A tipical setup, yielding good runtime results, is to use a RandomizedShuffleStrategy and a "smart" 3-way
 75///       <see cref="IThreeWayPartitionStrategy"/>, placing all pivot values in the middle segment. That variation of
 76///       the quicksort has expected worst-case Time Complexity linearithmic, i.e. has O(n * log(n)) Time Complexity
 77///       with high probability, and behaves almost linearly with many real case input configurations.
 78///     </para>
 79/// </remarks>
 80public class RecursiveQuickSort : IInputMutatingSort
 81{
 13882    private IShuffleStrategy ShuffleStrategy { get; }
 52183    private IThreeWayPartitionStrategy PartitionStrategy { get; }
 84
 85    /// <summary>
 86    /// Builds a sorter running quicksort with the provided <paramref name="partitionStrategy"/>.
 87    /// </summary>
 88    /// <param name="shuffleStrategy">
 89    /// The strategy used to shuffle the input list, before running the actual quicksort algorithm.
 90    /// </param>
 91    /// <param name="partitionStrategy">
 92    /// The strategy used to partition the sublist of the provided list within the provided start and end indices.
 93    /// </param>
 4894    public RecursiveQuickSort(IShuffleStrategy shuffleStrategy, IThreeWayPartitionStrategy partitionStrategy)
 4895    {
 4896        ShuffleStrategy = shuffleStrategy;
 4897        PartitionStrategy = partitionStrategy;
 4898    }
 99
 100    /// <inheritdoc path="//*[not(self::summary or self::remarks)]"/>
 101    /// <summary>
 102    ///     <inheritdoc/>
 103    ///     <br/>
 104    ///     Uses the quicksort algorithm with the default comparer for <typeparamref name="T"/>, given by
 105    ///     <see cref="Comparer{T}.Default"/>.
 106    /// </summary>
 107    /// <remarks>
 108    ///     <inheritdoc cref="RecursiveQuickSort"/>
 109    /// </remarks>
 110    public void Sort<T>(IList<T> list) where T : IComparable<T> =>
 114111        Sort(list, Comparer<T>.Default);
 112
 113    /// <inheritdoc path="//*[not(self::summary or self::remarks)]"/>
 114    /// <summary>
 115    ///     <inheritdoc/>
 116    ///     <br/>
 117    ///     Uses the quicksort algorithm with the specified <paramref name="comparer"/>.
 118    /// </summary>
 119    /// <remarks>
 120    ///     <inheritdoc cref="RecursiveQuickSort"/>
 121    /// </remarks>
 122    public void Sort<T>(IList<T> list, IComparer<T> comparer)
 138123    {
 138124        ShuffleStrategy.Shuffle(list, 0, list.Count - 1);
 138125        RecursiveSort(list, comparer, 0, list.Count - 1);
 138126    }
 127
 128    private void RecursiveSort<T>(IList<T> list, IComparer<T> comparer, int start, int end)
 1180129    {
 1839130        if (end - start <= 0) return;
 131
 521132        var (pivotLowIndex, pivotHighIndex) = PartitionStrategy.Partition(list, comparer, start, end);
 521133        RecursiveSort(list, comparer, start, pivotLowIndex - 1);
 521134        RecursiveSort(list, comparer, pivotHighIndex + 1, end);
 1180135    }
 136}
Generated by: ReportGenerator 5.1.19.0
03/19/2023 - 17:28:50
GitHub | reportgenerator.io

Methods/Properties

get_ShuffleStrategy()
get_PartitionStrategy()
.ctor(MoreStructures.Lists.Sorting.QuickSort.IShuffleStrategy,MoreStructures.Lists.Sorting.QuickSort.IThreeWayPartitionStrategy)
Sort(System.Collections.Generic.IList`1<T>)
Sort(System.Collections.Generic.IList`1<T>,System.Collections.Generic.IComparer`1<T>)
RecursiveSort(System.Collections.Generic.IList`1<T>,System.Collections.Generic.IComparer`1<T>,System.Int32,System.Int32)