| | | 1 | | namespace MoreStructures.Lists.Sorting; |
| | | 2 | | |
| | | 3 | | /// <summary> |
| | | 4 | | /// An <see cref="IInputMutatingSort"/> implementation based on selection sort. |
| | | 5 | | /// </summary> |
| | | 6 | | /// <remarks> |
| | | 7 | | /// <para id="advantages"> |
| | | 8 | | /// ADVANTAGES AND DISADVANTAGES |
| | | 9 | | /// <br/> |
| | | 10 | | /// - The algorithm performs sorting in place and is online. |
| | | 11 | | /// <br/> |
| | | 12 | | /// - It is not stable in its basic form and requires additional space or specific assumptions on the type of list |
| | | 13 | | /// being sorted (such as it being a linked list). |
| | | 14 | | /// <br/> |
| | | 15 | | /// - Compared to other quadratic comparison-based algorithms, such as <see cref="InsertionSort"/>, it is generally |
| | | 16 | | /// simpler but requires in average an higher number of comparisons, therefore yielding worse performance. |
| | | 17 | | /// <br/> |
| | | 18 | | /// - Compared to linearithmic comparison-based algorithms, such as <see cref="HeapSort"/>, it is way simpler to |
| | | 19 | | /// understand and predict in exact number of operations executed. However, the performance is sensibly worse. |
| | | 20 | | /// <br/> |
| | | 21 | | /// - Compared to non-comparison-based algorithms, such as counting sort, it doesn't require any assumption on the |
| | | 22 | | /// type or values of the items in the input, the only requirement being their total comparability and the |
| | | 23 | | /// comparison behaving according to total order operators rules. |
| | | 24 | | /// </para> |
| | | 25 | | /// <para id="algorithm"> |
| | | 26 | | /// ALGORITHM |
| | | 27 | | /// <br/> |
| | | 28 | | /// - This sorting algorithm split the list L being sorted in two parts: the sorted part, located at the beginning |
| | | 29 | | /// of the list (L[..i]), and the unsorted part, located at the end of the list (L[i..]). |
| | | 30 | | /// <br/> |
| | | 31 | | /// - At the beginning the sorted part is empty (i.e. length 0) and the unsorted part covers the entire list (i.e. |
| | | 32 | | /// length n). |
| | | 33 | | /// <br/> |
| | | 34 | | /// - The algorithm runs n iterations, where n is the number of items in the list. |
| | | 35 | | /// <br/> |
| | | 36 | | /// - At the beginning of iteration i, the sorted sub-list is L[..i] and the unsorted sub-list is L[i..]. |
| | | 37 | | /// <br/> |
| | | 38 | | /// - The unsorted sub-list L[i..] is scanned linearly, looking for the index j, between i and n - 1, of the item |
| | | 39 | | /// of L[i..] with minimum value. |
| | | 40 | | /// <br/> |
| | | 41 | | /// - L[i] is swapped with L[j] and the iteration i terminates. |
| | | 42 | | /// <br/> |
| | | 43 | | /// - Now L[..(i + 1)] is the new sorted sub-list, and L[(i + 1)..] is the new unsorted sub-list. |
| | | 44 | | /// </para> |
| | | 45 | | /// <para id="complexity"> |
| | | 46 | | /// COMPLEXITY |
| | | 47 | | /// <br/> |
| | | 48 | | /// - Each of the n iterations runs n - i - 1 comparisons, to identify the index of the item with the minimum value |
| | | 49 | | /// in the sub-list L[i..]. |
| | | 50 | | /// <br/> |
| | | 51 | | /// - The total number of comparisons, over the n iterations, is around n * n / 2. |
| | | 52 | | /// <br/> |
| | | 53 | | /// - Therefore, Time Complexity is O(n^2) and Space Complexity is O(1), since the algorithm runs in place. |
| | | 54 | | /// </para> |
| | | 55 | | /// </remarks> |
| | | 56 | | public class SelectionSort : IInputMutatingSort |
| | | 57 | | { |
| | | 58 | | /// <inheritdoc path="//*[not(self::summary or self::remarks)]"/> |
| | | 59 | | /// <summary> |
| | | 60 | | /// <inheritdoc/> |
| | | 61 | | /// <br/> |
| | | 62 | | /// Uses the selection sort algorithm with the default comparer for <typeparamref name="T"/>, given by |
| | | 63 | | /// <see cref="Comparer{T}.Default"/>. |
| | | 64 | | /// </summary> |
| | | 65 | | /// <remarks> |
| | | 66 | | /// <inheritdoc cref="SelectionSort"/> |
| | | 67 | | /// </remarks> |
| | | 68 | | public void Sort<T>(IList<T> list) where T : IComparable<T> => |
| | 19 | 69 | | Sort(list, Comparer<T>.Default); |
| | | 70 | | |
| | | 71 | | /// <inheritdoc path="//*[not(self::summary or self::remarks)]"/> |
| | | 72 | | /// <summary> |
| | | 73 | | /// <inheritdoc/> |
| | | 74 | | /// <br/> |
| | | 75 | | /// Uses the selection sort algorithm with the specified <paramref name="comparer"/>. |
| | | 76 | | /// </summary> |
| | | 77 | | /// <remarks> |
| | | 78 | | /// <inheritdoc cref="SelectionSort"/> |
| | | 79 | | /// </remarks> |
| | | 80 | | public void Sort<T>(IList<T> list, IComparer<T> comparer) |
| | 23 | 81 | | { |
| | 334 | 82 | | for (var i = 0; i < list.Count; i++) |
| | 144 | 83 | | { |
| | 144 | 84 | | var k = SelectIndexOfSmallestItem(list, comparer, i); |
| | 144 | 85 | | (list[i], list[k]) = (list[k], list[i]); |
| | 144 | 86 | | } |
| | 23 | 87 | | } |
| | | 88 | | |
| | | 89 | | private static int SelectIndexOfSmallestItem<T>(IList<T> list, IComparer<T> comparer, int startIndex) |
| | 144 | 90 | | { |
| | 144 | 91 | | int smallestItemIndex = startIndex; |
| | 1150 | 92 | | for (var j = startIndex + 1; j < list.Count; j++) |
| | 431 | 93 | | if (comparer.Compare(list[j], list[startIndex]) < 0) |
| | 56 | 94 | | smallestItemIndex = j; |
| | 144 | 95 | | return smallestItemIndex; |
| | 144 | 96 | | } |
| | | 97 | | } |