Class QuickSortCharsSorter

An implementation of ICharsSorter which uses QuickSort to sort the input.

Inheritance
System.Object
QuickSortCharsSorter
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.Strings.Sorting
Assembly: MoreStructures.dll
Syntax
public class QuickSortCharsSorter : ICharsSorter
Remarks

ADVANTAGES
The algorithm uses the QuickSort implementation of LINQ to sort strings, seen as lists of chars.
Being based on a comparison-based sorting algorithm, unlike the Counting Sort implementation, it doesn't leverage a linear runtime.
However, its runtime only depends on the size of the input, and it doesn't depend on the size of the alphabet.
Because of that, it is suitable for scenarios of large alphabets, or where there is no upper bound on the number of distinct chars in the input, other than the size of the alphabet.
For example: when the input string to be sorted is an unconstrained Unicode string.

ALGORITHM
- It uses the LINQ-provided QuickSort, to sort the couples defined by (index, char), for each char of the text, in ascending order.
- Then, it selects the indexes from the sorted sequence of instances, building and returning the position list.

COMPLEXITY
- The execution of the QuickSort has a runtime of O(n * log(n)).
- Output is not produced in-place, but a new list of n items is created.
- Therefore, Time Complexity is O(n * log(n)) and Space Complexity is O(n).

Constructors

| Improve this Doc View Source

QuickSortCharsSorter(Nullable<Char>)

Declaration
public QuickSortCharsSorter(char? maybeTerminator)
Parameters
Type Name Description
System.Nullable<System.Char> maybeTerminator

The char, if any, to be treated as terminator char when comparing chars of the input. If not specified, for System.Char will be used for char comparison.
Remarks

Methods

| Improve this Doc View Source

Sort(String)

Declaration
public IList<int> Sort(string input)
Parameters
Type Name Description
System.String input
Returns
Type Description
IList<System.Int32>
Remarks

Implements

Extension Methods