< Summary

Information
Class: MoreStructures.Lists.Sorting.ShellSort
Assembly: MoreStructures
File(s): /home/runner/work/MoreStructures/MoreStructures/MoreStructures/Lists/Sorting/ShellSort.cs
Line coverage
100%
Covered lines: 16
Uncovered lines: 0
Coverable lines: 16
Total lines: 129
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_GapGenerator()100%1100%
.ctor(...)100%1100%
Sort(...)100%1100%
Sort(...)100%2100%

File(s)

/home/runner/work/MoreStructures/MoreStructures/MoreStructures/Lists/Sorting/ShellSort.cs

#LineLine coverage
 1namespace MoreStructures.Lists.Sorting;
 2
 3/// <summary>
 4/// An <see cref="IInputMutatingSort"/> implementation based on Shell sort.
 5/// </summary>
 6/// <remarks>
 7///     <para id="advantages">
 8///     ADVANTAGES AND DISADVANTAGES
 9///     <br/>
 10///     - Compared to <see cref="InsertionSort"/>, it has better runtime, because it reduces the total number of
 11///       swapping operations performed.
 12///       <br/>
 13///     - That comes the cost of its complexity, which is higher than <see cref="InsertionSort"/> since Shell sort
 14///       requires execution of <see cref="InsertionSort"/> on multiple interleaved lists.
 15///       <br/>
 16///     - However, its performance heavily depends on the chosen gap sequence, with best cases being O(n * log(n)) and
 17///       worst cases being O(n^2), depending on the gap sequence.
 18///       <br/>
 19///     - Its average complexity characterization is to this day an open problem, and its lack of predictability is
 20///       one of its main drawbacks.
 21///       <br/>
 22///     - Unlike <see cref="InsertionSort"/>, it is not stable, i.e. it doesn't preserve the order of items in the
 23///       input with the same sorting key. This is due to the fact that the algorithm performs sorting of the subset of
 24///       the input with the highest gap first, potentially skipping first occurrences of some of the duplicated items.
 25///     </para>
 26///     <para id="algorithm">
 27///     ALGORITHM
 28///     <br/>
 29///     - This sorting algorithm runs the basic insertion sort algorithm, multiple times and with multiple steps.
 30///       <br/>
 31///     - In a standard insertion sort, comparisons and swapping at the iteration i of the main loop of the algorithm
 32///       are always made between items at consecutive locations, going back until the i-th item is placed in order
 33///       w.r.t. all preceding items.
 34///       <br/>
 35///     - That means that large items appearing early in the input will be swapped many times, before reaching their
 36///       final position in the input.
 37///       <br/>
 38///     - For example the items 5 to 9 in the input [5, 6, 7, 8, 9, 0, 1, 2, 3, 4] are swapped to make room for the
 39///       items 0 to 4. After 4 iterations, the iteration with i = 5 places 0 correctly by shifting from 9 all the way
 40///       down to 5. Same with all following iterations, with a total of 5 * 5 = 25 swapping operations before the
 41///       value 9 gets into its final place.
 42///       <br/>
 43///     - The idea behind Shell sort is that it gives the chance to bigger values to be placed closer to their final
 44///       position, faster than insertion sort.
 45///       <br/>
 46///     - It does that by sorting via insertion sort not just once and for the entire input, but multiple times and on
 47///       different sub-sets of it. Sub-sets are appropriately chosen, in a way that bigger values require less
 48///       swapping before getting to their final place.
 49///       <br/>
 50///     - The first sub-set of indexes sorted is defined by all locations of the input which are at a relative distance
 51///       equal to the gap. The gap is first set at its highest value and then decreased at every iteration.
 52///       <br/>
 53///     - Gap sequence is externally provided. For example, if the sequence provided is the powers of 2, the actual gap
 54///       sequence used for an input of 10 items is [8, 4, 2, 1] (8 is the highest power of 2 smaller than 10).
 55///       <br/>
 56///     - After the 1st run of insertion sort (gap = 8), the list is [2, 6, 7, 8, 9, 0, 1, 5, 3, 4].
 57///       <br/>
 58///     - After the 2nd run of insertion sort (gap = 4), the list is [2, 6, 7, 8, 4, 0, 1, 5, 3, 9].
 59///       <br/>
 60///     - As visible from the example, after only 3 comparisons, both the smallest and biggest items are already in
 61///       place.
 62///     </para>
 63///     <para id="complexity">
 64///     COMPLEXITY
 65///     <br/>
 66///     - Space Complexity is always O(1), since the algorithm runs in place.
 67///       <br/>
 68///     - Time Complexity, however, is strictly connected to the gap sequence selected.
 69///       <br/>
 70///     - Worst-case performance is O(n^2), assuming worst-case gap sequence, and O(n * log^2(n)), assuming best-case
 71///       gap sequence.
 72///       <br/>
 73///     - Best-case performance is O(n * log^2(n)), assuming worst-case gap sequence, and O(n * log(n)), assuming
 74///       best-case gap sequence.
 75///       <br/>
 76///     - Best-case performance is still O(n * log(n)) for most gap sequences in general.
 77///     </para>
 78/// </remarks>
 79public class ShellSort : IInputMutatingSort
 80{
 81    /// <summary>
 82    /// A generator of a monotonically strictly increasing sequence of <see cref="int"/>, each representing a gap
 83    /// between locations of the input.
 84    /// </summary>
 9285    protected IEnumerable<int> GapGenerator { get; }
 86
 87    /// <inheritdoc cref="ShellSort"/>
 88    /// <param name="gapGenerator">
 89    ///     <inheritdoc cref="GapGenerator" path="/summary"/>
 90    /// </param>
 3291    public ShellSort(IEnumerable<int> gapGenerator)
 3292    {
 3293        GapGenerator = gapGenerator;
 3294    }
 95
 96    /// <inheritdoc path="//*[not(self::summary or self::remarks)]"/>
 97    /// <summary>
 98    ///     <inheritdoc/>
 99    ///     <br/>
 100    ///     Uses the Shell sort algorithm with the default comparer for <typeparamref name="T"/>, given by
 101    ///     <see cref="Comparer{T}.Default"/>.
 102    /// </summary>
 103    /// <remarks>
 104    ///     <inheritdoc cref="ShellSort"/>
 105    /// </remarks>
 106    public void Sort<T>(IList<T> list) where T : IComparable<T> =>
 76107        Sort(list, Comparer<T>.Default);
 108
 109    /// <inheritdoc path="//*[not(self::summary or self::remarks)]"/>
 110    /// <summary>
 111    ///     <inheritdoc/>
 112    ///     <br/>
 113    ///     Uses the Shell sort algorithm with the specified <paramref name="comparer"/>.
 114    /// </summary>
 115    /// <remarks>
 116    ///     <inheritdoc cref="ShellSort"/>
 117    /// </remarks>
 118    public void Sort<T>(IList<T> list, IComparer<T> comparer)
 92119    {
 92120        var count = list.Count;
 92121        var gaps = GapGenerator
 361122            .TakeWhile(gap => gap < count)
 92123            .Reverse();
 814124        foreach (var gap in gaps)
 269125        {
 269126            InsertionSortHelpers.InsertionSortOnHthIndexes(list, comparer, gap);
 269127        }
 92128    }
 129}
Generated by: ReportGenerator 5.1.19.0
03/19/2023 - 17:28:50
GitHub | reportgenerator.io

Methods/Properties

get_GapGenerator()
.ctor(System.Collections.Generic.IEnumerable`1<System.Int32>)
Sort(System.Collections.Generic.IList`1<T>)
Sort(System.Collections.Generic.IList`1<T>,System.Collections.Generic.IComparer`1<T>)