Class RecursiveQuickSort

An IInputMutatingSort implementation based on the quicksort algorithm.

Inheritance

System.Object

RecursiveQuickSort

Implements

IInputMutatingSort

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 RecursiveQuickSort : IInputMutatingSort

Remarks

ADVANTAGES AND DISADVANTAGES
- Like MergeSort, it belongs to the category of linearithmic comparison-based sorting algorithm (when setup correctly, see the complexity analysis section below).
- Compared to MergeSort, it is in-place, having O(1) Space Complexity.
- However, it is not stable and it's not as easy parallelizable as MergeSort.
- While it is not optimal in the exact number of comparisons (it does in average 39% more comparisons than MergeSort, which is optimal on the number of comparisons), it does way less swapping and moving operations, resulting in a visibly better performance, especially when cost of moving items is high.
- For that reason is tipically the algorithm of choice when sorting primitive values or value types, such as struct instances, where cost of comparison is low and cost of swapping can be high, depending on the size of the struct.
- When sorting reference types, such as class instances, MergeSort is sometimes preferred, since swapping items in the list means swapping their references, which are of fixed and small size, and instead the cost of comparison can be quite high, depending on the or on the implementation used.
- Compared to most other comparison-based algorithms, a disadvantage of quicksort is that, for it to have consistently good performances, it has to be randomized. In such setup, it is not deterministic.

ALGORITHM
- First, it shuffles the input to sort, by using the IShuffleStrategy provided in the constructor.
- Then, it partitions the shuffled input into three segments: left, middle and right.
- Partitioning is done via the IThreeWayPartitionStrategy provided in the constructor. The way in which partitions are done, and in particular whether pivot values only appear in the middle segment, only in left and/or right segments or in all three segments, depends on the specific strategy used.
- In either case, the left contains items non-bigger than the pivot (possibly including pivot values), the middle items equal to the pivot (and no other values) and the right items non-smaller than the pivot (possibly including pivot values).
- Items in the middle segments have already been placed by the algorithm in their final position. Therefore, the middle segment doesn't have to be sorted any further. Left and rights segments, instead, are not sorted.
- So the algorithm calls recursively the quicksort on the left and right segments, to sort them.
- When the recursion terminates, the entire list is sorted.

COMPLEXITY
- Worst-case Time Complexity is O(n^2) and Space Complexity is O(1), since sorting happens entirely in place, by repeated swapping.
- Expected Time Complexity heavily depends on the choice of IShuffleStrategy and IThreeWayPartitionStrategy, which in turns depends on the choice of IPivotSelectionStrategy.
- For example, using IdentityShuffleStrategy and StartIndexPivotSelectionStrategy with inputs already sorted in ascending order, makes quicksort selects the worst pivot at every iteration, partitioning each window of the input list in the most unbalanced way (left segment empty and right segment containing all items but the pivot), and making quicksort behaving quadratically.
- The same happens when using IdentityShuffleStrategy and EndIndexPivotSelectionStrategy, with inputs already sorted in descending order.
- A tipical setup, yielding good runtime results, is to use a RandomizedShuffleStrategy and a "smart" 3-way IThreeWayPartitionStrategy, placing all pivot values in the middle segment. That variation of the quicksort has expected worst-case Time Complexity linearithmic, i.e. has O(n * log(n)) Time Complexity with high probability, and behaves almost linearly with many real case input configurations.

Constructors

RecursiveQuickSort(IShuffleStrategy, IThreeWayPartitionStrategy)

Builds a sorter running quicksort with the provided partitionStrategy.

Declaration

public RecursiveQuickSort(IShuffleStrategy shuffleStrategy, IThreeWayPartitionStrategy partitionStrategy)

Parameters

Type	Name	Description
IShuffleStrategy	shuffleStrategy	The strategy used to shuffle the input list, before running the actual quicksort algorithm.
IThreeWayPartitionStrategy	partitionStrategy	The strategy used to partition the sublist of the provided list within the provided start and end indices.

Methods

Sort<T>(IList<T>)

Uses the quicksort 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

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

Uses the quicksort 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

IInputMutatingSort

Extension Methods

SuffixStructureNodeExtensions.GetAllSuffixesFor<TEdge, TNode>(TNode, TextWithTerminator)