Class LomutoThreeWayPartitionStrategy

A IThreeWayPartitionStrategy implementing the Lomuto partition scheme into three segments, the middle containing only and all the items equals to the pivot.

Inheritance
System.Object
LomutoThreeWayPartitionStrategy
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 LomutoThreeWayPartitionStrategy : IThreeWayPartitionStrategy
Remarks

ADVANTAGES
- Compared to LomutoTwoWayPartitionStrategy it has the advantage of not making quicksort quadratic when many duplicates are present, since it places all the duplicates in the middle segment, which is not recursed over.
- This advantage comes, however, at the cost of its complexity, since two pointers and three non-empty segments have to be setup and kept coherent throughout the entire execution of the partitioning algorithm.
- Other advantages and disadvantages over other partitioning schemes, such as HoareTwoWayPartitionStrategy are described in the documentation of LomutoTwoWayPartitionStrategy.

ALGORITHM
- The algorithm closely resembles the one defined in LomutoTwoWayPartitionStrategy: pivot selection, using the provided PivotSelectionStrategy and swapping with L[end] happen in exactly the same way.
- Instead of a single pointer, two pointers i1 and i2 are defined: to the last index of the left segment, and to the first index of the right segment, set to start - 1 and start respectively.
- A running pointer j goes from the start index to the index before the end (the end index contains the pivot).
- Each item L[j] smaller than the pivot is added after the end of the left segment, which is increased by 1.
- In order to make room for L[j] in the left segment, the middle segment is "shifted" by one index on the right, more precisely by moving the first item of the middle segment after its end, and placing the first item of the right segment in position j.
- Each item L[j] equal to the pivot is added after the end of the middle segment, which is increased by 1.
- 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 increase i2.
- 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, middle 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 i1, the middle from i1 + 1 to i2 (at least an item, possibly more than one) and the right going from i2 + 1 to end.
- So, (i1 + 1, i2) 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 two swap and three increments are performed (j and possibly i1 and i2).
- 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

LomutoThreeWayPartitionStrategy(IPivotSelectionStrategy)

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

Declaration
public LomutoThreeWayPartitionStrategy(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