< Summary

Information
Class: MoreStructures.Lists.Sorting.QuickSort.LomutoThreeWayPartitionStrategy
Assembly: MoreStructures
File(s): /home/runner/work/MoreStructures/MoreStructures/MoreStructures/Lists/Sorting/QuickSort/LomutoThreeWayPartitionStrategy.cs
Line coverage
100%
Covered lines: 30
Uncovered lines: 0
Coverable lines: 30
Total lines: 120
Line coverage: 100%
Branch coverage
100%
Covered branches: 6
Total branches: 6
Branch coverage: 100%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
get_PivotSelectionStrategy()100%1100%
.ctor(...)100%1100%
Partition(...)100%6100%

File(s)

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

#LineLine coverage
 1namespace MoreStructures.Lists.Sorting.QuickSort;
 2
 3/// <summary>
 4/// A <see cref="IThreeWayPartitionStrategy"/> implementing the Lomuto partition scheme into three segments, the
 5/// middle containing only and all the items equals to the pivot.
 6/// </summary>
 7/// <remarks>
 8///     <para id="advantages">
 9///     ADVANTAGES
 10///     <br/>
 11///     - Compared to <see cref="LomutoTwoWayPartitionStrategy"/> it has the advantage of not making quicksort
 12///       quadratic when many duplicates are present, since it places all the duplicates in the middle segment,
 13///       which is not recursed over.
 14///       <br/>
 15///     - This advantage comes, however, at the cost of its complexity, since two pointers and three non-empty segments
 16///       have to be setup and kept coherent throughout the entire execution of the partitioning algorithm.
 17///       <br/>
 18///     - Other advantages and disadvantages over other partitioning schemes, such as
 19///       HoareTwoWayPartitionStrategy are described in the documentation of
 20///       <see cref="LomutoTwoWayPartitionStrategy"/>.
 21///     </para>
 22///     <para id="algorithm">
 23///     ALGORITHM
 24///     <br/>
 25///     - The algorithm closely resembles the one defined in <see cref="LomutoTwoWayPartitionStrategy"/>:
 26///       pivot selection, using the provided <see cref="PivotSelectionStrategy"/> and swapping with L[end] happen in
 27///       exactly the same way.
 28///       <br/>
 29///     - Instead of a single pointer, two pointers i1 and i2 are defined: to the last index of the left segment, and
 30///       to the first index of the right segment, set to start - 1 and start respectively.
 31///       <br/>
 32///     - A running pointer j goes from the start index to the index before the end (the end index contains the pivot).
 33///       <br/>
 34///     - Each item L[j] smaller than the pivot is added after the end of the left segment, which is increased by 1.
 35///       <br/>
 36///     - In order to make room for L[j] in the left segment, the middle segment is "shifted" by one index on the
 37///       right, more precisely by moving the first item of the middle segment after its end, and placing the first
 38///       item of the right segment in position j.
 39///       <br/>
 40///     - Each item L[j] equal to the pivot is added after the end of the middle segment, which is increased by 1.
 41///       <br/>
 42///     - In this case there is no need to touch the left segment, and it's enough to swap L[i2] with L[j], and then
 43///       increase i2.
 44///       <br/>
 45///     - By the time j will have run through all indices except the last, all items except the last will have been
 46///       partitioned into a left, middle and right segments.
 47///       <br/>
 48///     - By incrementing i one more time and swapping L[i] with L[end], the pivot goes into the right position, and
 49///       the three segments are in place: the left going from start to i1, the middle from i1 + 1 to i2 (at least an
 50///       item, possibly more than one) and the right going from i2 + 1 to end.
 51///       <br/>
 52///     - So, <c>(i1 + 1, i2)</c> is returned as result.
 53///     </para>
 54///     <para id="complexity">
 55///     COMPLEXITY
 56///     <br/>
 57///     - Pivot selection complexity depends on the specific <see cref="IPivotSelectionStrategy"/> strategy
 58///       used, and is not included in this analysis (i.e. it is assumed to be O(1)).
 59///       <br/>
 60///     - Pivot swapping, before and after the main loop, are both constant-time operations.
 61///       <br/>
 62///     - The main loop goes through n - 1 items, where n is the number of items in the window.
 63///       <br/>
 64///     - At each iteration, at most two swap and three increments are performed (j and possibly i1 and i2).
 65///       <br/>
 66///     - Therefore Time Complexity is O(n) and Space Complexity is O(1), since all swaps happen in-place on L.
 67///     </para>
 68/// </remarks>
 69public class LomutoThreeWayPartitionStrategy : IThreeWayPartitionStrategy
 70{
 71    /// <summary>
 72    /// The strategy to select the pivot.
 73    /// </summary>
 81874    public IPivotSelectionStrategy PivotSelectionStrategy { get; }
 75
 76    /// <summary>
 77    /// Builds a Lomuto 3-way partitioner with the provided <paramref name="pivotSelectionStrategy"/>.
 78    /// </summary>
 79    /// <param name="pivotSelectionStrategy">
 80    ///     <inheritdoc cref="PivotSelectionStrategy"/>
 81    /// </param>
 2782    public LomutoThreeWayPartitionStrategy(IPivotSelectionStrategy pivotSelectionStrategy)
 2783    {
 2784        PivotSelectionStrategy = pivotSelectionStrategy;
 2785    }
 86
 87    /// <inheritdoc path="//*[not(self::remarks)]"/>
 88    /// <remarks>
 89    ///     <inheritdoc/>
 90    ///     <inheritdoc cref="LomutoThreeWayPartitionStrategy"/>
 91    /// </remarks>
 92    public (int, int) Partition<T>(IList<T> list, IComparer<T> comparer, int start, int end)
 81893    {
 81894        var pivotIndex = PivotSelectionStrategy.Select(list, comparer, start, end);
 81895        (list[end], list[pivotIndex]) = (list[pivotIndex], list[end]);
 96
 81897        var pivot = list[end];
 81898        var i1 = start - 1;
 81899        var i2 = start;
 5644100        for (var j = start; j < end; j++)
 2004101        {
 2004102            var comparisonResult = comparer.Compare(list[j], pivot);
 2004103            if (comparisonResult < 0)
 848104            {
 848105                i1++;
 848106                (list[i2], list[j]) = (list[j], list[i2]);
 848107                (list[i1], list[i2]) = (list[i2], list[i1]);
 848108                i2++;
 848109            }
 1156110            else if (comparisonResult == 0)
 96111            {
 96112                (list[i2], list[j]) = (list[j], list[i2]);
 96113                i2++;
 96114            }
 2004115        }
 116
 818117        (list[i2], list[end]) = (list[end], list[i2]);
 818118        return (i1 + 1, i2);
 818119    }
 120}
Generated by: ReportGenerator 5.1.19.0
03/19/2023 - 17:28:50
GitHub | reportgenerator.io

Methods/Properties

get_PivotSelectionStrategy()
.ctor(MoreStructures.Lists.Sorting.QuickSort.IPivotSelectionStrategy)
Partition(System.Collections.Generic.IList`1<T>,System.Collections.Generic.IComparer`1<T>,System.Int32,System.Int32)