C# クイックソートと挿入ソートの組み合わせによるソート
クイックソートの分割配列が一定の要素数になったら挿入ソートに切り替えることにより、クイックソートを高速化する手法の実装である。
using System; using System.Collections.Generic; class Program { private static void Swap<T>(ref T a, ref T b) { T tmp = a; a = b; b = tmp; } public static void InsertionSort<T>(T[] arr, Int32 start, Int32 end, Comparison<T> comparison) { Int32 i, j; for (i = start + 1; i <= end; i++) { T tmp = arr[i]; for (j = i; j > 0 && comparison(arr[j - 1], tmp) > 0; j--) { arr[j] = arr[j - 1]; } arr[j] = tmp; } } private static T MedianOfThree<T>(T a, T b, T c) where T : IComparable<T> { if (a.CompareTo(b) >= 0) { if (a.CompareTo(c) <= 0) { return a; } } if (b.CompareTo(c) >= 0) { if (b.CompareTo(a) <= 0) { return b; } } if (c.CompareTo(a) >= 0) { if (c.CompareTo(b) <= 0) { return c; } } return b; } private static void QuickSortWithInsertionSort<T>(T[] arr, Int32 left, Int32 right, Comparison<T> comparison) where T : IComparable<T> { const Int32 MinimumDividedArraySize = 20; Int32 pl = left; Int32 pr = right; T pivot = MedianOfThree(arr[pl], arr[(pl + pr) / 2], arr[pr]); do { while (comparison(arr[pl], pivot) < 0) pl++; while (comparison(arr[pr], pivot) > 0) pr--; if (pl <= pr) { Swap(ref arr[pl], ref arr[pr]); pl++; pr--; } } while (pl <= pr); if (pr - left <= MinimumDividedArraySize) { InsertionSort(arr, left, pr, comparison); } else if (left < pr) { QuickSortWithInsertionSort(arr, left, pr, comparison); } if (right - pl <= MinimumDividedArraySize) { InsertionSort(arr, pl, right, comparison); } else if (pl < right) { QuickSortWithInsertionSort(arr, pl, right, comparison); } } public static void QuickSortWithInsertionSort<T>(T[] arr, Comparison<T> comparison) where T : IComparable<T> { QuickSortWithInsertionSort(arr, 0, arr.Length - 1, comparison); } public static void Main() { const Int32 N = 100; Int32[] a = new Int32[N]; Random rand = new Random(); for (Int32 i = 0; i < a.Length; i++) { a[i] = rand.Next() % a.Length; } QuickSortWithInsertionSort(a, delegate(Int32 x, Int32 y) { return x.CompareTo(y); }); Array.ForEach(a, delegate(Int32 n) { Console.WriteLine(n); }); } }