| | | 1 | | namespace MoreStructures.Lists.Sorting; |
| | | 2 | | |
| | | 3 | | /// <summary> |
| | | 4 | | /// An <see cref="IInputMutatingSort"/> implementation based on insertion sort. |
| | | 5 | | /// </summary> |
| | | 6 | | /// <remarks> |
| | | 7 | | /// <para id="algorithm"> |
| | | 8 | | /// ALGORITHM |
| | | 9 | | /// <br/> |
| | | 10 | | /// - This sorting algorithm split the list L being sorted in two parts: the sorted part, located at the beginning |
| | | 11 | | /// of the list (L[..i]), and the unsorted part, located at the end of the list (L[i..]). |
| | | 12 | | /// <br/> |
| | | 13 | | /// - At the beginning the sorted part is empty (i.e. length 0) and the unsorted part covers the entire list (i.e. |
| | | 14 | | /// length n). |
| | | 15 | | /// <br/> |
| | | 16 | | /// - The algorithm runs n - 1 1-based iterations, where n is the number of items in the list. |
| | | 17 | | /// <br/> |
| | | 18 | | /// - At the beginning of iteration i, the sorted sub-list is L[..i] and the unsorted sub-list is L[i..]. |
| | | 19 | | /// <br/> |
| | | 20 | | /// - The first item L[i], of the unsorted sub-list L[i..], is compared against its predecessor, L[i - 1]. |
| | | 21 | | /// <br/> |
| | | 22 | | /// - If L[i] is smaller than L[i - 1], the two items are swapped and the new L[i - 1] is compared with L[i - 2]. |
| | | 23 | | /// Comparisons and swapping continues until the predecessor is not bigger than its successor, potentially until |
| | | 24 | | /// the head of the list is reached. |
| | | 25 | | /// <br/> |
| | | 26 | | /// - When a L[j] is found, which is not strictly smaller than L[j - 1], L[.. (i + 1)] is sorted, and the iteration |
| | | 27 | | /// i can terminate. |
| | | 28 | | /// </para> |
| | | 29 | | /// <para id="complexity"> |
| | | 30 | | /// COMPLEXITY |
| | | 31 | | /// <br/> |
| | | 32 | | /// - Each of the n - 1 iterations runs at most i - 1 comparisons, if it has to swap all the way up to the head of |
| | | 33 | | /// the list. |
| | | 34 | | /// <br/> |
| | | 35 | | /// - The total number of comparisons, over the n iterations, is around n * n / 2. |
| | | 36 | | /// <br/> |
| | | 37 | | /// - Therefore, Time Complexity is O(n^2) and Space Complexity is O(1), since the algorithm runs in place and |
| | | 38 | | /// hence only requires additional constant space to perform the sorting. |
| | | 39 | | /// </para> |
| | | 40 | | /// </remarks> |
| | | 41 | | public class InsertionSort : IInputMutatingSort |
| | | 42 | | { |
| | | 43 | | /// <inheritdoc path="//*[not(self::summary or self::remarks)]"/> |
| | | 44 | | /// <summary> |
| | | 45 | | /// <inheritdoc/> |
| | | 46 | | /// <br/> |
| | | 47 | | /// Uses the insertion sort algorithm with the default comparer for <typeparamref name="T"/>, given by |
| | | 48 | | /// <see cref="Comparer{T}.Default"/>. |
| | | 49 | | /// </summary> |
| | | 50 | | /// <remarks> |
| | | 51 | | /// <inheritdoc cref="InsertionSort"/> |
| | | 52 | | /// </remarks> |
| | | 53 | | public void Sort<T>(IList<T> list) where T : IComparable<T> => |
| | 19 | 54 | | Sort(list, Comparer<T>.Default); |
| | | 55 | | |
| | | 56 | | /// <inheritdoc path="//*[not(self::summary or self::remarks)]"/> |
| | | 57 | | /// <summary> |
| | | 58 | | /// <inheritdoc/> |
| | | 59 | | /// <br/> |
| | | 60 | | /// Uses the insertion sort algorithm with the specified <paramref name="comparer"/>. |
| | | 61 | | /// </summary> |
| | | 62 | | /// <remarks> |
| | | 63 | | /// <inheritdoc cref="InsertionSort"/> |
| | | 64 | | /// </remarks> |
| | | 65 | | public void Sort<T>(IList<T> list, IComparer<T> comparer) => |
| | 23 | 66 | | InsertionSortHelpers.InsertionSortOnHthIndexes(list, comparer, 1); |
| | | 67 | | } |