Class ShellSort

An IInputMutatingSort implementation based on Shell sort.

Inheritance
System.Object
ShellSort
Implements
Inherited Members
System.Object.Equals(System.Object)
System.Object.Equals(System.Object, System.Object)
System.Object.GetHashCode()
System.Object.GetType()
System.Object.MemberwiseClone()
System.Object.ReferenceEquals(System.Object, System.Object)
System.Object.ToString()
Namespace: MoreStructures.Lists.Sorting
Assembly: MoreStructures.dll
Syntax
public class ShellSort : IInputMutatingSort
Remarks

ADVANTAGES AND DISADVANTAGES
- Compared to InsertionSort, it has better runtime, because it reduces the total number of swapping operations performed.
- That comes the cost of its complexity, which is higher than InsertionSort since Shell sort requires execution of InsertionSort on multiple interleaved lists.
- However, its performance heavily depends on the chosen gap sequence, with best cases being O(n * log(n)) and worst cases being O(n^2), depending on the gap sequence.
- Its average complexity characterization is to this day an open problem, and its lack of predictability is one of its main drawbacks.
- Unlike InsertionSort, it is not stable, i.e. it doesn't preserve the order of items in the input with the same sorting key. This is due to the fact that the algorithm performs sorting of the subset of the input with the highest gap first, potentially skipping first occurrences of some of the duplicated items.

ALGORITHM
- This sorting algorithm runs the basic insertion sort algorithm, multiple times and with multiple steps.
- In a standard insertion sort, comparisons and swapping at the iteration i of the main loop of the algorithm are always made between items at consecutive locations, going back until the i-th item is placed in order w.r.t. all preceding items.
- That means that large items appearing early in the input will be swapped many times, before reaching their final position in the input.
- 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 items 0 to 4. After 4 iterations, the iteration with i = 5 places 0 correctly by shifting from 9 all the way down to 5. Same with all following iterations, with a total of 5 * 5 = 25 swapping operations before the value 9 gets into its final place.
- The idea behind Shell sort is that it gives the chance to bigger values to be placed closer to their final position, faster than insertion sort.
- It does that by sorting via insertion sort not just once and for the entire input, but multiple times and on different sub-sets of it. Sub-sets are appropriately chosen, in a way that bigger values require less swapping before getting to their final place.
- The first sub-set of indexes sorted is defined by all locations of the input which are at a relative distance equal to the gap. The gap is first set at its highest value and then decreased at every iteration.
- Gap sequence is externally provided. For example, if the sequence provided is the powers of 2, the actual gap sequence used for an input of 10 items is [8, 4, 2, 1] (8 is the highest power of 2 smaller than 10).
- After the 1st run of insertion sort (gap = 8), the list is [2, 6, 7, 8, 9, 0, 1, 5, 3, 4].
- After the 2nd run of insertion sort (gap = 4), the list is [2, 6, 7, 8, 4, 0, 1, 5, 3, 9].
- As visible from the example, after only 3 comparisons, both the smallest and biggest items are already in place.

COMPLEXITY
- Space Complexity is always O(1), since the algorithm runs in place.
- Time Complexity, however, is strictly connected to the gap sequence selected.
- Worst-case performance is O(n^2), assuming worst-case gap sequence, and O(n * log^2(n)), assuming best-case gap sequence.
- Best-case performance is O(n * log^2(n)), assuming worst-case gap sequence, and O(n * log(n)), assuming best-case gap sequence.
- Best-case performance is still O(n * log(n)) for most gap sequences in general.

Constructors

| Improve this Doc View Source

ShellSort(IEnumerable<Int32>)

Declaration
public ShellSort(IEnumerable<int> gapGenerator)
Parameters
Type Name Description
IEnumerable<System.Int32> gapGenerator

Properties

| Improve this Doc View Source

GapGenerator

A generator of a monotonically strictly increasing sequence of System.Int32, each representing a gap between locations of the input.

Declaration
protected IEnumerable<int> GapGenerator { get; }
Property Value
Type Description
IEnumerable<System.Int32>

Methods

| Improve this Doc View Source

Sort<T>(IList<T>)


Uses the Shell sort algorithm with the default comparer for T, given by .

Declaration
public void Sort<T>(IList<T> list)
    where T : IComparable<T>
Parameters
Type Name Description
IList<T> list
Type Parameters
Name Description
T
Remarks

| Improve this Doc View Source

Sort<T>(IList<T>, IComparer<T>)


Uses the Shell sort algorithm with the specified comparer.

Declaration
public void Sort<T>(IList<T> list, IComparer<T> comparer)
Parameters
Type Name Description
IList<T> list
IComparer<T> comparer
Type Parameters
Name Description
T
Remarks

Implements

Extension Methods