< Summary

Information
Class: MoreStructures.Lists.Sorting.QuickSort.LomutoTwoWayPartitionStrategy
Assembly: MoreStructures
File(s): /home/runner/work/MoreStructures/MoreStructures/MoreStructures/Lists/Sorting/QuickSort/LomutoTwoWayPartitionStrategy.cs
Line coverage
100%
Covered lines: 22
Uncovered lines: 0
Coverable lines: 22
Total lines: 127
Line coverage: 100%
Branch coverage
100%
Covered branches: 4
Total branches: 4
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%4100%

File(s)

/home/runner/work/MoreStructures/MoreStructures/MoreStructures/Lists/Sorting/QuickSort/LomutoTwoWayPartitionStrategy.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 always being a single pivot.
 6/// </summary>
 7/// <remarks>
 8///     <para id="advantages">
 9///     ADVANTAGES
 10///     <br/>
 11///     - Compared to <see cref="LomutoThreeWayPartitionStrategy"/> and HoareTwoWayPartitionStrategy, it
 12///       is simpler, since it only requires a single pointer.
 13///       <br/>
 14///     - However it makes quicksort quadratic when many duplicates are present, because it places all the duplicates
 15///       of the pivot in the right segment.
 16///       <br/>
 17///     - Notice that the same would happen if the strict inequality on the comparison result done in partitioning
 18///       would have been replaced by a non-strict inequality, because in that scenarios all duplicates would have been
 19///       placed in the left segment.
 20///       <br/>
 21///     - Only a randomized strategy, not implemented by this strategy, could have distributed evenly pivots in the two
 22///       partitions.
 23///       <br/>
 24///     - <see cref="LomutoThreeWayPartitionStrategy"/> solves this problem differently, by placing all pivots in the
 25///       middle segment. That, however, requires 2 indices and its more complex because it generates three segments
 26///       which can contain more than 1 element each, including the middle segment.
 27///       <br/>
 28///     - HoareTwoWayPartitionStrategy addresses the problem by still using two pointers, but running
 29///       from the two extremes of the window, inwards. That distributes the duplicates evenly (in average, over non
 30///       pathological input lists) and only generates two segments, with the middle segment empty.
 31///       <br/>
 32///     - Both <see cref="LomutoTwoWayPartitionStrategy"/> and <see cref="LomutoThreeWayPartitionStrategy"/> perform
 33///       three times more swaps than HoareTwoWayPartitionStrategy on average.
 34///       <br/>
 35///     </para>
 36///     <para id="algorithm">
 37///     ALGORITHM
 38///     <br/>
 39///     - First, the index ip, of the item of the list acting as pivot, is selected, using the provided
 40///       <see cref="PivotSelectionStrategy"/>.
 41///       <br/>
 42///     - L[ip] is swapped with L[end], i.e. the pivot is moved at the end of the window.
 43///       <br/>
 44///     - Then, the value of the pivot p is taken from the list being sorted L, from the last item of the window, where
 45///       it has just been placed.
 46///       <br/>
 47///     - A pointer i is defined, to point to the frontier between values smaller than p, and more precisely to the
 48///       last index of the left segment, which is also the index before the first index of the current middle segment.
 49///       <br/>
 50///     - Its initial value is start - 1, since at the beginning the left segment is empty.
 51///       <br/>
 52///     - A running pointer j goes from the start index to the index before the end (the end index contains the pivot).
 53///       <br/>
 54///     - For each item L[j] smaller than the pivot, i is increased, to augment the left segment of one item, and items
 55///       at positions i and j are swapped, to accomodate L[j] in the left segment, since it is smaller than the pivot.
 56///       <br/>
 57///     - That moves the previous L[i] beyond the frontier, and that is correct, since it is non-smaller than the
 58///       pivot.
 59///       <br/>
 60///     - By the time j will have run through all indices except the last, all items except the last will have been
 61///       partitioned into a left and right segments.
 62///       <br/>
 63///     - By incrementing i one more time and swapping L[i] with L[end], the pivot goes into the right position, and
 64///       the three segments are in place: the left going from start to i - 1, the middle from i to i (single item) and
 65///       the right going from i + 1 to end.
 66///       <br/>
 67///     - So, <c>(i, i)</c> is returned as result.
 68///     </para>
 69///     <para id="complexity">
 70///     COMPLEXITY
 71///     <br/>
 72///     - Pivot selection complexity depends on the specific <see cref="IPivotSelectionStrategy"/> strategy
 73///       used, and is not included in this analysis (i.e. it is assumed to be O(1)).
 74///       <br/>
 75///     - Pivot swapping, before and after the main loop, are both constant-time operations.
 76///       <br/>
 77///     - The main loop goes through n - 1 items, where n is the number of items in the window.
 78///       <br/>
 79///     - At each iteration, at most a swap and two increments are performed (j and possibly i).
 80///       <br/>
 81///     - Therefore Time Complexity is O(n) and Space Complexity is O(1), since all swaps happen in-place on L.
 82///     </para>
 83/// </remarks>
 84public class LomutoTwoWayPartitionStrategy : IThreeWayPartitionStrategy
 85{
 86    /// <summary>
 87    /// The strategy to select the pivot.
 88    /// </summary>
 87989    public IPivotSelectionStrategy PivotSelectionStrategy { get; }
 90
 91    /// <summary>
 92    /// Builds a Lomuto 2-way partitioner with the provided <paramref name="pivotSelectionStrategy"/>.
 93    /// </summary>
 94    /// <param name="pivotSelectionStrategy">
 95    ///     <inheritdoc cref="PivotSelectionStrategy"/>
 96    /// </param>
 2797    public LomutoTwoWayPartitionStrategy(IPivotSelectionStrategy pivotSelectionStrategy)
 2798    {
 2799        PivotSelectionStrategy = pivotSelectionStrategy;
 27100    }
 101
 102    /// <inheritdoc path="//*[not(self::remarks)]"/>
 103    /// <remarks>
 104    ///     <inheritdoc/>
 105    ///     <inheritdoc cref="LomutoTwoWayPartitionStrategy"/>
 106    /// </remarks>
 107    public (int, int) Partition<T>(IList<T> list, IComparer<T> comparer, int start, int end)
 879108    {
 879109        var pivotIndex = PivotSelectionStrategy.Select(list, comparer, start, end);
 879110        (list[end], list[pivotIndex]) = (list[pivotIndex], list[end]);
 111
 879112        var pivot = list[end];
 879113        var i = start - 1;
 5996114        for (var j = start; j < end; j++)
 2119115        {
 2119116            if (comparer.Compare(list[j], pivot) < 0)
 872117            {
 872118                i++;
 872119                (list[i], list[j]) = (list[j], list[i]);
 872120            }
 2119121        }
 122
 879123        i++;
 879124        (list[end], list[i]) = (list[i], list[end]);
 879125        return (i, i);
 879126    }
 127}
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)