| | | 1 | | using MoreLinq; |
| | | 2 | | using MoreStructures.Utilities; |
| | | 3 | | |
| | | 4 | | namespace MoreStructures.Strings.Sorting; |
| | | 5 | | |
| | | 6 | | /// <summary> |
| | | 7 | | /// An implementation of <see cref="ICharsSorter"/> which uses QuickSort to sort the input. |
| | | 8 | | /// </summary> |
| | | 9 | | /// <remarks> |
| | | 10 | | /// <para id="advantages"> |
| | | 11 | | /// ADVANTAGES |
| | | 12 | | /// <br/> |
| | | 13 | | /// The algorithm uses the QuickSort implementation of LINQ to sort strings, seen as lists of chars. |
| | | 14 | | /// <br/> |
| | | 15 | | /// Being based on a comparison-based sorting algorithm, unlike the Counting Sort implementation, it doesn't |
| | | 16 | | /// leverage a linear runtime. |
| | | 17 | | /// <br/> |
| | | 18 | | /// However, its runtime only depends on the size of the input, and it doesn't depend on the size of the alphabet. |
| | | 19 | | /// <br/> |
| | | 20 | | /// Because of that, it is suitable for scenarios of large alphabets, or where there is no upper bound on the |
| | | 21 | | /// number of distinct chars in the input, other than the size of the alphabet. |
| | | 22 | | /// <br/> |
| | | 23 | | /// For example: when the input string to be sorted is an unconstrained Unicode string. |
| | | 24 | | /// </para> |
| | | 25 | | /// <para id="algo"> |
| | | 26 | | /// ALGORITHM |
| | | 27 | | /// <br/> |
| | | 28 | | /// - It uses the LINQ-provided QuickSort, to sort the <see cref="KeyValuePair"/> couples defined by (index, char), |
| | | 29 | | /// for each char of the text, in ascending order. |
| | | 30 | | /// <br/> |
| | | 31 | | /// - Then, it selects the indexes from the sorted sequence of <see cref="KeyValuePair"/> instances, building and |
| | | 32 | | /// returning the position list. |
| | | 33 | | /// </para> |
| | | 34 | | /// <para id="complexity"> |
| | | 35 | | /// COMPLEXITY |
| | | 36 | | /// <br/> |
| | | 37 | | /// - The execution of the QuickSort has a runtime of O(n * log(n)). |
| | | 38 | | /// <br/> |
| | | 39 | | /// - Output is not produced in-place, but a new list of n items is created. |
| | | 40 | | /// <br/> |
| | | 41 | | /// - Therefore, Time Complexity is O(n * log(n)) and Space Complexity is O(n). |
| | | 42 | | /// </para> |
| | | 43 | | /// </remarks> |
| | | 44 | | public class QuickSortCharsSorter : ICharsSorter |
| | | 45 | | { |
| | 19 | 46 | | private IComparer<char> CharsComparer { get; } |
| | | 47 | | |
| | | 48 | | /// <summary> |
| | | 49 | | /// <inheritdoc cref="QuickSortCharsSorter"/> |
| | | 50 | | /// </summary> |
| | | 51 | | /// <param name="maybeTerminator"> |
| | | 52 | | /// The char, if any, to be treated as terminator char when comparing chars of the input. |
| | | 53 | | /// If not specified, <see cref="Comparer{T}.Default"/> for <see cref="char"/> will be used for char comparison. |
| | | 54 | | /// </param> |
| | | 55 | | /// <remarks> |
| | | 56 | | /// <inheritdoc cref="QuickSortCharsSorter"/> |
| | | 57 | | /// </remarks> |
| | 19 | 58 | | public QuickSortCharsSorter(char? maybeTerminator) |
| | 19 | 59 | | { |
| | 19 | 60 | | CharsComparer = maybeTerminator != null |
| | 19 | 61 | | ? CharOrTerminatorComparer.Build(maybeTerminator.Value) |
| | 19 | 62 | | : Comparer<char>.Default; |
| | 19 | 63 | | } |
| | | 64 | | |
| | | 65 | | /// <inheritdoc path="//*[not(self::remarks)]"/> |
| | | 66 | | /// <remarks> |
| | | 67 | | /// <inheritdoc cref="QuickSortCharsSorter" path="/remarks"/> |
| | | 68 | | /// </remarks> |
| | | 69 | | public IList<int> Sort(string input) |
| | 19 | 70 | | { |
| | 19 | 71 | | return input |
| | 19 | 72 | | .Index() |
| | 86 | 73 | | .OrderBy(kvp => kvp.Value, CharsComparer) |
| | 86 | 74 | | .Select(kvp => kvp.Key) |
| | 19 | 75 | | .ToList(); |
| | 19 | 76 | | } |
| | | 77 | | } |