Изучение спроса: алгоритмы сортировки на C#

Формулировка задачи:

Предлагаю к вашему вниманию статический класс SortHelper, в котом реализованы различные виды сортировок и их оптимизаций: 1. Быстрая сортировка (2 шт.) 2. Сортировка Шелла. 3. Сортировка вставками (2 шт.) 4. Выбором 5. Пузырьковая. Если тема будет пользоваться спросом, то будут добавлены: 1. Пирамидальная сортировка 2. Сортировка слиянием. 3. интроспективная сортировка (быстрая + пирамидальная) 4. сортировка Седжвика (быстрая + вставками). 5. Dual-pivot quicksort. Чтобы пощупать/ потестировать/ сравнить. Прилагаю код для тестирования и измерения времени работы алгоритмов для целочисленных массивов.

 
using System;
 
namespace Algorithms
{
    public static class SortHelper<T> where T : IComparable
    {
        #region Быстрая сортировка
        public static void QSort(T[] a)
        {
            QuickSort1(a, 0, a.Length - 1);
        }
 
        //Быстрая сортировка с выбором опороного элемента по медиане из 3 элементов 
        //и с контролем переполнения стека.
        private static void QuickSort1(T[] keys, int left, int right)
        {
            do
            {
                int a = left;
                int b = right;
                int m = a + ((b - a) >> 1);
                CompareSwap(keys, a, m);
                CompareSwap(keys, a, b);
                CompareSwap(keys,  m, b);
                T p = keys[m];
 
                do
                {
                    while (keys[a].CompareTo(p) < 0) ++a; 
                    while (p.CompareTo(keys[b]) < 0) --b; 
                    if (a > b) break; 
                    if (a < b)
                    {
                        T t = keys[a]; keys[a] = keys[b]; keys[b] = t;
                    }
                    a++;
                    b--;
                }
                while (a <= b);
                if (b - left <= right - a)
                {
                    if (left < b)
                    {
                        QuickSort1(keys, left, b);
                    }
                    left = a;
                }
                else
                {
                    if (a < right)
                    {
                        QuickSort1(keys, a, right);
                    }
                    right = b;
                }
            }
            while (left < right);
        }
 
        public static void StupidQuickSort(T[] a)
        {
            QuickSortBase(a, 0, a.Length - 1);
        }
 
        //Быстрая сортировка без оптимизаций, упадет с переполнением стека
        //на 100000 элементах
        private static void QuickSortBase(T[] a, int l, int r)
        {
            if(l >= r) return;
            int i = Partition(a, l, r);
            QuickSortBase(a, l, i - 1);
            QuickSortBase(a, i + 1, r);
        }
 
        private static int Partition(T[] a, int l, int r)
        {
            T v = a[r];
            int i = l - 1;
            int j = r;
            do
            {
                while (a[++i].CompareTo(v) < 0) ;
                while (v.CompareTo(a[--j]) < 0) if(i==j) break;
                if(i >= j) break;
                Swap(ref a[i], ref a[j]);
            } 
            while (true);
            Swap(ref a[r], ref a[i]);
            return i;
        }
        #endregion
 
        #region Сортировка Шелла
        //Сортировка Шелла
        public static void ShellSort(T[] a)
        {
            int h;
            for (h = 1; h <= a.Length/9; h = 3*h + 1) ;
            for (; h > 0; h /= 3)
            {
                for (int i = h; i < a.Length; ++i)
                {
                    T t = a[i];
                    int j = i;
                    while (j >=h && a[j - h].CompareTo(t) > 0)
                    {
                        a[j] = a[j - h];
                        j -= h;
                    }
                    a[j] = t;
                }
            }
        }
        #endregion
 
        #region Сортировка вставками
        //оптимизированная сортировка вставками:
        //1. Используется сигнальный элемент
        //2. Обмен заменен на сдвиг.
        //   работает в 2 раза быстрее обменной сортировки вставками
        public static void InsertionSort2(T[] a)
        {
            for (int i = a.Length - 1; i > 0; --i)
                if (a[i].CompareTo(a[i - 1]) < 0)
                    Swap(ref a[i - 1], ref a[i]);
            for (int i = 2; i < a.Length; ++i)
            {
                T t = a[i];
                int j = i;
                while (a[j - 1].CompareTo(t) > 0)
                {
                    a[j] = a[j - 1];
                    --j;
                }
                a[j] = t;
            }
        }
 
        //обменная сортировка вставками
        public static void InsertionSort(T[] a)
        {
            for (int i = 1; i < a.Length; ++i)
                for (int j = i; j > 0 && (a[j - 1].CompareTo(a[j]) > 0); --j)
                    Swap(ref a[j - 1], ref a[j]);
        }
 
        #endregion
 
        #region Пузырьковая и выбором
        //Не адаптивная
        public static void BubleSort(T[] a)
        {
            for (int i = 0; i < a.Length; ++i)
                for (int j = a.Length - 1; j > i; --j)
                    if (a[j].CompareTo(a[j - 1]) < 0)
                        Swap(ref a[j - 1], ref a[j]);
        }
 
        public static void SelectionSort(T[] a)
        {
            for (int i = 0; i < a.Length - 1; ++i)
            {
                int min = i;
                for (int j = i + 1; j < a.Length; ++j)
                {
                    if (a[j].CompareTo(a[min]) < 0) min = j;
                }
                Swap(ref a[i], ref a[min]);
            }
        }
 
        #endregion
 
        #region Вспомогательные методы
        private static void Swap(ref T a, ref T b)
        {
            T t = a; a = b; b = t;
        }
 
        private static void CompareSwap(T[] keys, int a, int b)
        {
            if ((a != b) && (keys[a].CompareTo(keys[b])) > 0)
            {
                T t = keys[a]; keys[a] = keys[b]; keys[b] = t;
            }
        }
        #endregion
    }
}

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
 
namespace Algorithms
{
    class Program
    {
        static void Main(string[] args)
        {
            SortStartTesterInfo startTester3 = new SortStartTesterInfo(SortHelper<int>.QSort, Console.Out);
            startTester3.TestCount = 10;
            startTester3.MinArrayLength = 1000000;
            startTester3.MaxArrayLength = 1000000;
            startTester3.MinValue = int.MinValue;
            startTester3.MaxValue = int.MaxValue;
            SortEndTesterInfo res3 = SortTester.Test(startTester3);
            Console.WriteLine(res3);
            Console.ReadKey();
        }
 
        public sealed class SortEndTesterInfo
        {
            public bool IsError { get; set; }
            public int ErrorTestNumber { get; set; }
            public TimeSpan Averagetime { get; set; }
 
            public override string ToString()
            {
                if (IsError)
                    return "Error!";
                return string.Format("Average elapsed time: {0:00}:{1:00}:{2:00}.{3:000}",
                    Averagetime.Hours, Averagetime.Minutes, Averagetime.Seconds, Averagetime.Milliseconds);
            }
        }
 
        public sealed class SortStartTesterInfo
        {
            public Action<int[]> Sort { get; private set; }
            public int TestCount { get; set; }
            public int MinArrayLength { get; set; }
            public int MaxArrayLength { get; set; }
            public int MinValue { get; set; }
            public int MaxValue { get; set; }
 
            public bool IsTrace { get { return Writer != null; } }
            public TextWriter Writer { get; private set; }
            public bool PrintArray { get; set; }
 
            public SortStartTesterInfo(Action<int[]> sort, TextWriter writer = null)
            {
                Debug.Assert(sort != null);
                Sort = sort;
                TestCount = 10;
                MinArrayLength = 1;
                MaxArrayLength = 20;
                MinValue = -10;
                MaxValue = 10;
                Writer = writer;
                PrintArray = false;
            }
        }
 
        public static class SortTester
        {
            public static SortEndTesterInfo Test(SortStartTesterInfo startInfo)
            {
                SortEndTesterInfo result = new SortEndTesterInfo();
                var source = GenerateArrays(startInfo.TestCount, startInfo.MinArrayLength, startInfo.MaxArrayLength, startInfo.MinValue, startInfo.MaxValue);
                double avg = 0;
                int i = 1;
                foreach(var array in source)
                {
                    if (startInfo.IsTrace)
                    {
                        startInfo.Writer.WriteLine();
                        startInfo.Writer.WriteLine("--------------------------------------------");
                        startInfo.Writer.WriteLine("begin test #{0} ", i);
                        if (startInfo.PrintArray)
                        {
                            startInfo.Writer.Write("Source array: ");
                            ArrayHelper.PrintArray(array, startInfo.Writer);
                        }
                    }
                    TimeSpan time = Sort(array, startInfo.Sort);
                    avg += time.TotalMilliseconds / startInfo.TestCount;
                    bool res = ArrayHelper.IsSorted(array);
                    if (startInfo.IsTrace)
                    {
                        startInfo.Writer.WriteLine("end test #{0}", i);
                        startInfo.Writer.WriteLine("Elapsed time: {0:00}:{1:00}:{2:00}.{3:000}", time.Hours, time.Minutes, time.Seconds, time.Milliseconds);
                        startInfo.Writer.WriteLine("Result: {0}", res ? "OK" : "Error");
                        startInfo.Writer.WriteLine("--------------------------------------------");
                    }
                    if (!res)
                    {
                        result.IsError = true;
                        result.ErrorTestNumber = i;
                        return result;
                    }
                    ++i;
                }
                result.ErrorTestNumber = -1;
                result.IsError = false;
                result.Averagetime = TimeSpan.FromMilliseconds(avg);
                return result;
            }
 
            private static TimeSpan Sort(int[] a, Action<int[]> sort)
            {
                GC.Collect();
                GC.WaitForPendingFinalizers();
                GC.Collect();
                Stopwatch stopwatch = new Stopwatch();
                stopwatch.Start();
                sort(a);
                stopwatch.Stop();
                return stopwatch.Elapsed;
            }
 
            private static IEnumerable<int[]> GenerateArrays(int count, int minLen, int maxLen, int min, int max)
            {
                Random r = Sweets.CreateRandom();
                for (int i = 0; i < count; ++i)
                    yield return ArrayHelper.GenArray(r.Next(minLen, maxLen), min, max);
            }
        }
 
        public static class ArrayHelper
        {
            public static int[] GenArray(int count, int min, int max)
            {
                Random r = Sweets.CreateRandom();
                int[] a = new int[count];
                for (int i = 0; i < a.Length; ++i)
                    a[i] = r.Next(min, max);
                return a;
            }
 
            public static bool IsSorted<T>(T[] a) where T : IComparable
            {
                for (int i = 0; i < a.Length - 1; ++i)
                {
                    if (a[i].CompareTo(a[i + 1]) > 0)
                        return false;
                }
                return true;
            }
 
            public static void PrintArray<T>(T[] a, TextWriter writer)
            {
                writer.WriteLine(string.Join(" ", a));
            }
        }
 
        internal static class Sweets
        {
            public static Random CreateRandom()
            {
                return new Random((int)DateTime.Now.Ticks & 0x0000FFFF);
            }
        }
    }
}

Сразу оговорюсь, что ни каких проверок на дурака\отлов Exception в коде нет и не будет, т.к. этот код используется только для учебных целей. Просмотрел FAQ там есть сортировки, но несколько разрознено, а некоторые попросту не представлены. А так же для тех, кто считает, что изучение алгоритмов сортировки пустая трата времени: Проходите стороной

Решение задачи: «Изучение спроса: алгоритмы сортировки на C#»

textual
                            Листинг программы 
                        

                            using System;
 
namespace Algorithms
{
    public static class SortHelper<T> where T : IComparable<T>
    {
        private const int ISORT_MAX = 32;
 
        #region Сортировка слиянием
 
        public static void MergeSort(T[] a)
        {
            T[] aux = new T[a.Length];
            MergeSort(a, 0, a.Length - 1, aux);
        }
 
        public static void MergeSortBu(T[] a)
        {
            T[] aux = new T[a.Length];
            MergeSortBu(a, 0, a.Length - 1, aux);
        }
 
        private static void MergeSortBu(T[] a, int l, int r, T[] aux)
        {
            for (int m = 1; m <= r - l; m += m)
                for (int i = l; i <= r - m; i += 2*m)
                    Merge(a, i, i + m - 1, Math.Min(i + 2*m - 1, r), aux);
        }
 
        private static void MergeSort(T[] a, int l, int r, T[] aux)
        {
            if (l >= r) return;
            int m = (l + r) >> 1;
            MergeSort(a, l, m, aux);
            MergeSort(a, m + 1, r, aux);
            Merge(a, l, m, r, aux);
        }
 
        //процедура слияния
        //l - левая граница сортируемого массива, r - правая, m - медиана, т.е. середина (l+r)/2
        //т.е. абстрактно мы имеем два подмассива b[l..m] и с[m+1, r], которые требуется слить в массив a
        //aux - дополнительный массив, в который мы бедем копировать подмассивы b[1..m] и с[m+1..r],
        //располагая элменты таким образом, что за концом массива b будет следовать конец массива с,
        //это требуется для того, что не проверять на каждой итерации выход за границы массивов b и с
        private static void Merge(T[] a, int l, int m, int r, T[] aux)
        {
            int i, j;
            for (i = m + 1; i > l; --i) aux[i - 1] = a[i - 1];
            for (j = m; j < r; ++j) aux[r + m - j] = a[j + 1];
            for (int k = l; k <= r; ++k)
                a[k] = aux[j].CompareTo(aux[i]) < 0 ? aux[j--] : aux[i++];
        }
 
        #endregion
 
        #region Быстрая сортировка c переключением на сортировку вставками
 
        public static void QSort(T[] a)
        {
            QuickSort1(a, 0, a.Length - 1);
            InsSort(a, 0, a.Length - 1);
        }
 
        //Быстрая сортировка с выбором опороного элемента по медиане из 3 элементов 
        //и с контролем переполнения стека. 
        private static void QuickSort1(T[] keys, int left, int right)
        {
            do
            {
                int a = left;
                int b = right;
                int m = a + ((b - a) >> 1);
                CompareSwap(keys, a, m);
                CompareSwap(keys, a, b);
                CompareSwap(keys, m, b);
                T p = keys[m];
 
                do
                {
                    while (keys[a].CompareTo(p) < 0) ++a;
                    while (p.CompareTo(keys[b]) < 0) --b;
                    if (a > b) break;
                    if (a < b)
                    {
                        T t = keys[a];
                        keys[a] = keys[b];
                        keys[b] = t;
                    }
                    a++;
                    b--;
                } while (a <= b);
                if (b - left <= right - a)
                {
                    if (left < b)
                    {
                        QuickSort1(keys, left, b);
                    }
                    left = a;
                }
                else
                {
                    if (a < right)
                    {
                        QuickSort1(keys, a, right);
                    }
                    right = b;
                }
            } while (right - left >= ISORT_MAX);
        }
 
        public static void QSortBase(T[] a)
        {
            QuickSortBase(a, 0, a.Length - 1);
            InsSort(a, 0, a.Length - 1);
        }
 
        private static void QuickSortBase(T[] a, int l, int r)
        {
            if (r - l <= ISORT_MAX) return;
            int i = Partition(a, l, r);
            QuickSortBase(a, l, i - 1);
            QuickSortBase(a, i + 1, r);
        }
 
        private static int Partition(T[] a, int l, int r)
        {
            int m = l + ((r - l) >> 1);
            Swap(ref a[m], ref a[r - 1]);
            Med3(a, l, r - 1, r);
            int i = l - 1;
            int j = r;
            T v = a[r - 1];
            do
            {
                while (a[++i].CompareTo(v) < 0) ;
                while (v.CompareTo(a[--j]) < 0) ;
                if (i >= j) break;
                Swap(ref a[i], ref a[j]);
            } while (true);
            Swap(ref a[r-1], ref a[i]);
            return i;
        }
 
        #endregion
 
        #region Сортировка Шелла
 
        //Сортировка Шелла
        public static void ShellSort(T[] a)
        {
            int h;
            for (h = 1; h <= a.Length/9; h = 3*h + 1) ;
            for (; h > 0; h /= 3)
            {
                for (int i = h; i < a.Length; ++i)
                {
                    T t = a[i];
                    int j = i;
                    while (j >= h && a[j - h].CompareTo(t) > 0)
                    {
                        a[j] = a[j - h];
                        j -= h;
                    }
                    a[j] = t;
                }
            }
        }
 
        #endregion
 
        #region Сортировка вставками
 
        //отпимизированная сортировка вставками:
        //1. Используется сигнальный элемент
        //2. Обмен заменен на сдвиг.
        //   работает в 2 раза быстрее обменной сортировки вставками
        public static void InsertionSort2(T[] a)
        {
            for (int i = a.Length - 1; i > 0; --i)
                if (a[i].CompareTo(a[i - 1]) < 0)
                    Swap(ref a[i - 1], ref a[i]);
            for (int i = 2; i < a.Length; ++i)
            {
                T t = a[i];
                int j = i;
                while (a[j - 1].CompareTo(t) > 0)
                {
                    a[j] = a[j - 1];
                    --j;
                }
                a[j] = t;
            }
        }
 
        private static void InsSort(T[] a, int l, int r)
        {
            for (int i = l + 1; i <= r; ++i)
            {
                T t = a[i];
                int j = i;
                while (j > l && a[j - 1].CompareTo(t) > 0)
                {
                    a[j] = a[j - 1];
                    --j;
                }
                a[j] = t;
            }
        }
 
        //обменная сортировка вставками
        public static void InsertionSort(T[] a)
        {
            for (int i = 1; i < a.Length; ++i)
                for (int j = i; j > 0 && (a[j - 1].CompareTo(a[j]) > 0); --j)
                    Swap(ref a[j - 1], ref a[j]);
        }
 
        #endregion
 
        #region Пузырьковая, Расческой и выбором
 
        //Расческой (оптимизированный пузырек)
        //Идея простая: оставить как можно меньше малых значений к концу массива
        //В сортировки Шелла используется похожая идея 
        public static void CombSort(T[] a)
        {
            T swap;
            int h = a.Length;
            bool swapped = false;
 
            while ((h > 1) || swapped)
            {
                if (h > 1)
                    h = (int) (h/1.247330950103979);
 
                swapped = false;
 
                for (int i = 0; h + i < a.Length; ++i)
                {
                    if (a[i].CompareTo(a[i + h]) > 0)
                    {
                        swap = a[i];
                        a[i] = a[i + h];
                        a[i + h] = swap;
                        swapped = true;
                    }
                }
            }
        }
 
        //Неадаптивная
        public static void BubleSort(T[] a)
        {
            for (int i = 0; i < a.Length; ++i)
                for (int j = a.Length - 1; j > i; --j)
                    if (a[j].CompareTo(a[j - 1]) < 0)
                        Swap(ref a[j - 1], ref a[j]);
        }
 
        public static void SelectionSort(T[] a)
        {
            for (int i = 0; i < a.Length - 1; ++i)
            {
                int min = i;
                for (int j = i + 1; j < a.Length; ++j)
                {
                    if (a[j].CompareTo(a[min]) < 0) min = j;
                }
                Swap(ref a[i], ref a[min]);
            }
        }
 
        #endregion
 
        #region Вспомогательные методы
 
 
        private static void Swap(ref T a, ref T b)
        {
            T t = a;
            a = b;
            b = t;
        }
 
        private static void CompareSwap(T[] keys, int a, int b)
        {
            if ((a != b) && (keys[a].CompareTo(keys[b])) > 0)
            {
                T t = keys[a];
                keys[a] = keys[b];
                keys[b] = t;
            }
        }
 
        private static void Med3(T[] a, int l, int m, int r)
        {
            CompareSwap(a, l, m);
            CompareSwap(a, l, r);
            CompareSwap(a, m, r);
        }
 
        #endregion
 
        #region Выбор max, min, min_max, n-th element
 
        //помещает в N-ю позицию последовательности элемент, который мог бы быть в этой позиции, 
        //если бы последовательность была отсортирована.
        public static void NthElement(T[] a, int n)
        {
            NthElement(a, n, 0, a.Length - 1);
        }
 
        private static void NthElement(T[] a, int n, int l, int r)
        {
            while (l < r)
            {
                int i = Partition(a, l, r);
                if (n <= i)
                    r = i - 1;
                if (n >= i)
                    l = i + 1;
            }
        }
 
        public struct MinMaxIndexes
        {
            public readonly int Min;
            public readonly int Max;
 
            public MinMaxIndexes(int min, int max)
            {
                Min = min;
                Max = max;
            }
 
            public override string ToString()
            {
                return string.Format("min index: {0}; max index: {1}", Min, Max);
            }
        }
 
        public struct MinMax
        {
            public readonly T Min;
            public readonly T Max;
 
            public MinMax(T min, T max)
            {
                Min = min;
                Max = max;
            }
 
            public override string ToString()
            {
                return string.Format("min: {0}; max: {1}", Min, Max);
            }
        }
 
        public static int MaxIndexOf(T[] a)
        {
            int imax = 0;
            for (int i = 0; i < a.Length; ++i)
                if (a[imax].CompareTo(a[i]) < 0)
                    imax = i;
            return imax;
        }
 
        public static int MinIndexOf(T[] a)
        {
            int imin = 0;
            for (int i = 0; i < a.Length; ++i)
                if (a[imin].CompareTo(a[i]) > 0)
                    imin = i;
            return imin;
        }
 
        public static T Max(T[] a)
        {
            return a[MaxIndexOf(a)];
        }
 
        public static T Min(T[] a)
        {
            return a[MinIndexOf(a)];
        }
 
        public static MinMax FindMinMax(T[] a)
        {
            bool odd = (a.Length & 1) == 1;
            T min = a[0], max = a[0];
            int i = 1;
            if (!odd)
            {
                if (a[0].CompareTo(a[1]) > 0)
                    min = a[1];
                else if (a[0].CompareTo(a[1]) < 0)
                    max = a[1];
                ++i;
            }
 
            while (i < a.Length - 1)
            {
                if (a[i].CompareTo(a[i + 1]) >= 0)
                {
                    if (min.CompareTo(a[i + 1]) > 0)
                        min = a[i + 1];
                    if (max.CompareTo(a[i]) < 0)
                        max = a[i];
                }
                else if (a[i].CompareTo(a[i + 1]) < 0)
                {
                    if (min.CompareTo(a[i]) > 0)
                        min = a[i];
                    if (max.CompareTo(a[i + 1]) < 0)
                        max = a[i + 1];
                }
                i += 2;
            }
            return new MinMax(min, max);
        }
 
        public static MinMaxIndexes MinMaxIndicesOf(T[] a)
        {
            bool odd = (a.Length & 1) == 1;
            int imin = 0, imax = 0, i = 1;
            if (!odd)
            {
                if (a[0].CompareTo(a[1]) > 0)
                    ++imin;
                else if (a[0].CompareTo(a[1]) < 0)
                    ++imax;
                ++i;
            }
            while (i < a.Length - 1)
            {
                if (a[i].CompareTo(a[i + 1]) > 0)
                {
                    if (a[imin].CompareTo(a[i + 1]) > 0)
                        imin = i + 1;
                    if (a[imax].CompareTo(a[i]) < 0)
                        imax = i;
                }
                else if (a[i].CompareTo(a[i + 1]) < 0)
                {
                    if (a[imin].CompareTo(a[i]) > 0)
                        imin = i;
                    if (a[imax].CompareTo(a[i + 1]) < 0)
                        imax = i + 1;
                }
                else
                {
                    if (a[imin].CompareTo(a[i]) > 0)
                        imin = i;
                    if (a[imax].CompareTo(a[i]) < 0)
                        imax = i;
                }
                i += 2;
            }
            return new MinMaxIndexes(imin, imax);
        }
        #endregion
    }
}
                        