This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revisionLast revisionBoth sides next revision | ||
fuss:csharp [2017/02/22 18:30] – external edit 127.0.0.1 | fuss:csharp [2021/05/08 03:22] – [Iterative] office | ||
---|---|---|---|
Line 1593: | Line 1593: | ||
var o = object.GetFP(" | var o = object.GetFP(" | ||
</ | </ | ||
+ | |||
+ | ====== Merge Sort ====== | ||
+ | |||
+ | ===== Recursive ===== | ||
+ | |||
+ | Recursively and using generics. | ||
+ | |||
+ | <code csharp> | ||
+ | using System; | ||
+ | |||
+ | namespace Sorts.MergeSort.Recursive | ||
+ | { | ||
+ | public class MergeSort | ||
+ | { | ||
+ | private static int[] List { get; set; } | ||
+ | |||
+ | public MergeSort(int[] list) | ||
+ | { | ||
+ | List = list; | ||
+ | } | ||
+ | |||
+ | public int[] Sort() | ||
+ | { | ||
+ | return Partition(List); | ||
+ | } | ||
+ | |||
+ | private static T[] Partition< | ||
+ | { | ||
+ | if (list.Length <= 1) | ||
+ | { | ||
+ | return list; | ||
+ | } | ||
+ | |||
+ | var pivot = list.Length / 2; | ||
+ | |||
+ | T[] l = new T[pivot]; | ||
+ | |||
+ | Array.Copy(list, | ||
+ | |||
+ | T[] r = new T[list.Length - pivot]; | ||
+ | |||
+ | Array.Copy(list, | ||
+ | |||
+ | return Merge(Partition(l), | ||
+ | } | ||
+ | |||
+ | private static T[] Concatenate< | ||
+ | { | ||
+ | T[] rest = new T[a.Length + b.Length]; | ||
+ | |||
+ | Array.Copy(a, | ||
+ | Array.Copy(b, | ||
+ | |||
+ | return rest; | ||
+ | } | ||
+ | |||
+ | private static T[] Concatenate< | ||
+ | { | ||
+ | T[] result = new T[l.Length + 1]; | ||
+ | result[0] = a; | ||
+ | |||
+ | Array.Copy(l, | ||
+ | |||
+ | return result; | ||
+ | } | ||
+ | |||
+ | private static T Car< | ||
+ | { | ||
+ | return l[0]; | ||
+ | } | ||
+ | |||
+ | private static T[] Cdr< | ||
+ | { | ||
+ | T[] cdr = new T[l.Length - 1]; | ||
+ | |||
+ | Array.Copy(l, | ||
+ | |||
+ | return cdr; | ||
+ | } | ||
+ | |||
+ | private static T[] Merge< | ||
+ | { | ||
+ | if (l.Length == 0 || r.Length == 0) | ||
+ | { | ||
+ | return Concatenate(l, | ||
+ | } | ||
+ | |||
+ | if (l[0].CompareTo(r[0]) > 0) | ||
+ | { | ||
+ | return Concatenate(Car(r), | ||
+ | } | ||
+ | |||
+ | return Concatenate(Car(l), | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | |||
+ | </ | ||
+ | |||
+ | May have stack issues so should be called by increasing the stack size: | ||
+ | <code csharp> | ||
+ | var t = new Thread(() => | ||
+ | { | ||
+ | list = new MergeSort.Recursive.MergeSort(list).Sort(); | ||
+ | |||
+ | }, 1024 * 1024 * 50); | ||
+ | |||
+ | t.Start(); | ||
+ | </ | ||
+ | |||
+ | ===== Iterative ===== | ||
+ | |||
+ | <code csharp> | ||
+ | using System; | ||
+ | |||
+ | namespace Sorts.MergeSort.Iterative | ||
+ | { | ||
+ | public class MergeSort | ||
+ | { | ||
+ | private static int[] List { get; set; } | ||
+ | |||
+ | public MergeSort(int[] list) | ||
+ | { | ||
+ | List = list; | ||
+ | } | ||
+ | |||
+ | public int[] Sort() | ||
+ | { | ||
+ | return Sort(List); | ||
+ | } | ||
+ | |||
+ | private static T Min< | ||
+ | { | ||
+ | return x.CompareTo(y) < 0 ? x : y; | ||
+ | } | ||
+ | |||
+ | private static T[] Sort< | ||
+ | { | ||
+ | T[] b = new T[a.Length]; | ||
+ | |||
+ | for (int size = 1; size < a.Length; size *= 2) | ||
+ | { | ||
+ | for (int left = 0; left + size < a.Length; left += size * 2) | ||
+ | { | ||
+ | int l = left + size; | ||
+ | int r = Min(l + size, a.Length); | ||
+ | |||
+ | var k = left; | ||
+ | var i = left; | ||
+ | var j = l; | ||
+ | while (i < l && j < r) | ||
+ | { | ||
+ | if (a[i].CompareTo(a[j]) < 0) | ||
+ | { | ||
+ | b[k] = a[i]; | ||
+ | ++i; | ||
+ | } | ||
+ | else | ||
+ | { | ||
+ | b[k] = a[j]; | ||
+ | ++j; | ||
+ | } | ||
+ | |||
+ | ++k; | ||
+ | } | ||
+ | while (i < l) | ||
+ | { | ||
+ | b[k] = a[i]; | ||
+ | ++i; | ||
+ | ++k; | ||
+ | } | ||
+ | |||
+ | while (j < r) | ||
+ | { | ||
+ | b[k] = a[j]; | ||
+ | ++j; | ||
+ | ++k; | ||
+ | } | ||
+ | |||
+ | for (k = left; k < r; ++k) | ||
+ | { | ||
+ | a[k] = b[k]; | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | |||
+ | return a; | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | |||
+ | </ | ||
+ | |||
+ | ====== Enable Double Buffering for Controls ====== | ||
+ | |||
+ | Some window forms controls do not expose the double buffering property such that the following static extension method will attempt to enable double buffering and return true on success or false otherwise. | ||
+ | |||
+ | <code csharp> | ||
+ | /// < | ||
+ | /// Enable double buffering for an arbitrary control. | ||
+ | /// </ | ||
+ | /// <param name=" | ||
+ | /// < | ||
+ | /// < | ||
+ | public static bool SetDoubleBuffered(this Control control) | ||
+ | { | ||
+ | if (SystemInformation.TerminalServerSession) | ||
+ | { | ||
+ | return false; | ||
+ | } | ||
+ | |||
+ | var dgvType = control.GetType(); | ||
+ | var pi = dgvType.GetProperty(" | ||
+ | BindingFlags.Instance | BindingFlags.NonPublic); | ||
+ | if (pi == null) | ||
+ | { | ||
+ | return false; | ||
+ | } | ||
+ | |||
+ | pi.SetValue(control, | ||
+ | |||
+ | return true; | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | Enabling double buffering can be particularly beneficial for '' | ||