| | | 1 | | using MoreStructures.PriorityQueues.BinaryHeap; |
| | | 2 | | |
| | | 3 | | namespace MoreStructures.Lists.Sorting; |
| | | 4 | | |
| | | 5 | | /// <summary> |
| | | 6 | | /// An <see cref="IInputMutatingSort"/> implementation based on heapsort. |
| | | 7 | | /// </summary> |
| | | 8 | | /// <remarks> |
| | | 9 | | /// <para id="algorithm"> |
| | | 10 | | /// ALGORITHM |
| | | 11 | | /// <br/> |
| | | 12 | | /// - This sorting algorithm relies entirely on the max binary heap data structure. |
| | | 13 | | /// <br/> |
| | | 14 | | /// - Given the list L to sort, it builds an heap H out of the entire list, passing L as backing structure for H. |
| | | 15 | | /// <br/> |
| | | 16 | | /// - H is defined at the end of L and with an inverted order, so that it always pops the current minimum from the |
| | | 17 | | /// root located at very end of the list, and leaves holes at the beginning of the list. |
| | | 18 | | /// <br/> |
| | | 19 | | /// - Then, it pops items from H, one by one, appending at the front of L, where the pop has left a hole. |
| | | 20 | | /// <br/> |
| | | 21 | | /// - For example if L is 10 items long, the first pop will leave the item at index 0 unoccupied, the second pop |
| | | 22 | | /// will leave the item at index 1 unoccupied (the item at index 0 already is out of the picture), etc. |
| | | 23 | | /// <br/> |
| | | 24 | | /// - Once the last item of H is popped, the heap is empty and L is sorted in ascending order. |
| | | 25 | | /// </para> |
| | | 26 | | /// <para id="complexity"> |
| | | 27 | | /// COMPLEXITY |
| | | 28 | | /// <br/> |
| | | 29 | | /// - Building a heap in batch from a list of n items takes a linear amount of time. |
| | | 30 | | /// <br/> |
| | | 31 | | /// - Each pop takes a logarithmic amount of time, due to the sift down required to restore the heap property. |
| | | 32 | | /// <br/> |
| | | 33 | | /// - Storing the popped item at the back of the list is a constant time operation. |
| | | 34 | | /// <br/> |
| | | 35 | | /// - Because the heap is built in place on the provided list, the list is never replicated in memroy and only a |
| | | 36 | | /// constant amount of additional space is required, for heap re-adjustment operations. |
| | | 37 | | /// <br/> |
| | | 38 | | /// - Therefore, Time Complexity is O(n * log(n)) and Space Complexity is O(1), where n is the number of items |
| | | 39 | | /// being sorted (which can be lower than the size of the provided list). |
| | | 40 | | /// </para> |
| | | 41 | | /// </remarks> |
| | | 42 | | public class HeapSort : IInputMutatingSort |
| | | 43 | | { |
| | | 44 | | /// <inheritdoc path="//*[not(self::summary or self::remarks)]"/> |
| | | 45 | | /// <summary> |
| | | 46 | | /// <inheritdoc/> |
| | | 47 | | /// <br/> |
| | | 48 | | /// Uses the heapsort algorithm with the default comparer for <typeparamref name="T"/>, given by |
| | | 49 | | /// <see cref="Comparer{T}.Default"/>. |
| | | 50 | | /// </summary> |
| | | 51 | | /// <remarks> |
| | | 52 | | /// <inheritdoc cref="HeapSort"/> |
| | | 53 | | /// </remarks> |
| | | 54 | | public void Sort<T>(IList<T> list) where T : IComparable<T> => |
| | 19 | 55 | | Sort(list, Comparer<T>.Default); |
| | | 56 | | |
| | | 57 | | /// <inheritdoc path="//*[not(self::summary or self::remarks)]"/> |
| | | 58 | | /// <summary> |
| | | 59 | | /// <inheritdoc/> |
| | | 60 | | /// <br/> |
| | | 61 | | /// Uses the heapsort algorithm with the specified <paramref name="comparer"/>. |
| | | 62 | | /// </summary> |
| | | 63 | | /// <remarks> |
| | | 64 | | /// <inheritdoc cref="HeapSort"/> |
| | | 65 | | /// </remarks> |
| | | 66 | | public void Sort<T>(IList<T> list, IComparer<T> comparer) |
| | 37 | 67 | | { |
| | 662 | 68 | | var reverseComparer = Comparer<T>.Create((x, y) => -comparer.Compare(x, y)); |
| | 37 | 69 | | var heap = new BinaryHeapListWrapper<T>(list, reverseComparer, list.Count, true); |
| | 37 | 70 | | var bufferLastAvailableIndex = 0; |
| | 233 | 71 | | while (heap.HeapCount > 0) |
| | 196 | 72 | | { |
| | 196 | 73 | | var maxItem = heap.Pop(); |
| | 196 | 74 | | heap[bufferLastAvailableIndex] = maxItem; |
| | 196 | 75 | | bufferLastAvailableIndex++; |
| | 196 | 76 | | } |
| | 37 | 77 | | } |
| | | 78 | | } |