Class LomutoTwoWayPartitionStrategy

A IThreeWayPartitionStrategy implementing the Lomuto partition scheme into three segments, the middle always being a single pivot.

Inheritance
System.Object
LomutoTwoWayPartitionStrategy
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.QuickSort
Assembly: MoreStructures.dll
Syntax
public class LomutoTwoWayPartitionStrategy : IThreeWayPartitionStrategy
Remarks

ADVANTAGES
- Compared to LomutoThreeWayPartitionStrategy and HoareTwoWayPartitionStrategy, it is simpler, since it only requires a single pointer.
- However it makes quicksort quadratic when many duplicates are present, because it places all the duplicates of the pivot in the right segment.
- Notice that the same would happen if the strict inequality on the comparison result done in partitioning would have been replaced by a non-strict inequality, because in that scenarios all duplicates would have been placed in the left segment.
- Only a randomized strategy, not implemented by this strategy, could have distributed evenly pivots in the two partitions.
- LomutoThreeWayPartitionStrategy solves this problem differently, by placing all pivots in the middle segment. That, however, requires 2 indices and its more complex because it generates three segments which can contain more than 1 element each, including the middle segment.
- HoareTwoWayPartitionStrategy addresses the problem by still using two pointers, but running from the two extremes of the window, inwards. That distributes the duplicates evenly (in average, over non pathological input lists) and only generates two segments, with the middle segment empty.
- Both LomutoTwoWayPartitionStrategy and LomutoThreeWayPartitionStrategy perform three times more swaps than HoareTwoWayPartitionStrategy on average.

ALGORITHM
- First, the index ip, of the item of the list acting as pivot, is selected, using the provided PivotSelectionStrategy.
- L[ip] is swapped with L[end], i.e. the pivot is moved at the end of the window.
- Then, the value of the pivot p is taken from the list being sorted L, from the last item of the window, where it has just been placed.
- A pointer i is defined, to point to the frontier between values smaller than p, and more precisely to the last index of the left segment, which is also the index before the first index of the current middle segment.
- Its initial value is start - 1, since at the beginning the left segment is empty.
- A running pointer j goes from the start index to the index before the end (the end index contains the pivot).
- For each item L[j] smaller than the pivot, i is increased, to augment the left segment of one item, and items at positions i and j are swapped, to accomodate L[j] in the left segment, since it is smaller than the pivot.
- That moves the previous L[i] beyond the frontier, and that is correct, since it is non-smaller than the pivot.
- By the time j will have run through all indices except the last, all items except the last will have been partitioned into a left and right segments.
- By incrementing i one more time and swapping L[i] with L[end], the pivot goes into the right position, and the three segments are in place: the left going from start to i - 1, the middle from i to i (single item) and the right going from i + 1 to end.
- So, (i, i) is returned as result.

COMPLEXITY
- Pivot selection complexity depends on the specific IPivotSelectionStrategy strategy used, and is not included in this analysis (i.e. it is assumed to be O(1)).
- Pivot swapping, before and after the main loop, are both constant-time operations.
- The main loop goes through n - 1 items, where n is the number of items in the window.
- At each iteration, at most a swap and two increments are performed (j and possibly i).
- Therefore Time Complexity is O(n) and Space Complexity is O(1), since all swaps happen in-place on L.

Constructors

| Improve this Doc View Source

LomutoTwoWayPartitionStrategy(IPivotSelectionStrategy)

Builds a Lomuto 2-way partitioner with the provided pivotSelectionStrategy.

Declaration
public LomutoTwoWayPartitionStrategy(IPivotSelectionStrategy pivotSelectionStrategy)
Parameters
Type Name Description
IPivotSelectionStrategy pivotSelectionStrategy

Properties

| Improve this Doc View Source

PivotSelectionStrategy

The strategy to select the pivot.

Declaration
public IPivotSelectionStrategy PivotSelectionStrategy { get; }
Property Value
Type Description
IPivotSelectionStrategy

Methods

| Improve this Doc View Source

Partition<T>(IList<T>, IComparer<T>, Int32, Int32)

Declaration
public (int, int) Partition<T>(IList<T> list, IComparer<T> comparer, int start, int end)
Parameters
Type Name Description
IList<T> list
IComparer<T> comparer
System.Int32 start
System.Int32 end
Returns
Type Description
System.ValueTuple<System.Int32, System.Int32>
Type Parameters
Name Description
T
Remarks

Implements

Extension Methods