Алгоритмы сортировки и их производительность

Прежде чем перейти к статье, хочу вам представить, экономическую онлайн игру Brave Knights, в которой вы можете играть и зарабатывать. Регистируйтесь, играйте и зарабатывайте!

Вступление

Здравствуйте, давно читаю Хабр и все хотел написать кому-нибудь статью, но не знал с чего начать и о чем писать. Но решил что тянуть кота за причинное место. Надо просто взять и написать обзор о чем то что я знаю и что будет просто для начало. Поэтому решил описать алгоритмы сортировки в размере 37 штук. Я понимаю, что на Хабре есть подобные статьи, одна постараюсь их добавить количеством алгоритмов и приведением небольшого числа графиков.

Список алгоритмов

Bubble
Shaker
Insertion
Stooge
Pancake
Shell
Merge
Selection
Quick
Gnome
Tree
Comb
BasicCounting
CombinedBubble
Heapify
Cocktail
OddEven
Tim
Counting
Radix
Bucket
BinaryInsertion
Bogo
Cycle
Exchange
Heap
MSDRadix

Ниже представлена таблица с основными характеристиками алгоритмов сортировок.

Название	Время			Память
Название	Лучшее	Среднее	Худшее	Память
Bubble		$O(n^{2})$	$O(n^{2})$
Shaker		$O(n^{2})$	$O(n^{2})$
Insertion		$O(n^{2})$	$O(n^{2})$
Stooge	$O(\frac{a^{log 3}}{log 1.5})$	$O(\frac{a^{log 3}}{log 1.5})$	$O(\frac{a^{log 3}}{log 1.5})$
Pancake		$O(n^{2})$	$O(n^{2})$
Shell	$O(n\times log^{2}n)$	Зависит от выбора шага	$O(n^{2})$
Merge	$O(n\times logn)$	$O(n\times logn)$	$O(n\times logn)$
Selection	$O(n^{2})$	$O(n^{2})$	$O(n^{2})$
Quick	$O(n\times logn)$	$O(n\times logn)$	$O(n^{2})$
Gnome		$O(n^{2})$	$O(n^{2})$
Tree		$O(n\times logn)$	$O(n\times logn)$
Comb		$O(\frac{n^2}{2^p})$	$O(n^{2})$
BasicCounting
CombinedBubble		$O(n^{2})$	$O(n^{2})$
Heapify	$O(n\times logn)$	$O(n\times logn)$	$O(n\times logn)$
Cocktail		$O(n^{2})$	$O(n^{2})$
OddEven		$O(n^{2})$	$O(n^{2})$
Tim		$O(n\times logn)$	$O(n\times logn)$
Counting
Radix	$O(n\times k)$	$O(n\times k)$
Bucket	$O(n^{2})$	$O(n\times k)$
BinaryInsertion		$O(n\times logn)$	$O(n\times logn)$
Bogo		$O(n\times n!)$	$O(n\times n!)$
Cycle		$O(n^{2})$	$O(n^{2})$
Exchange	$O(n^{2})$	$O(n^{2})$	$O(n^{2})$
Heap	$O(n\times logn)$	$O(n\times logn)$	$O(n\times logn)$
MSDRadix	$O(n\times k)$	$O(n\times k)$	$O(n\times logn)$

Описание алгоритмов

Bubble

Алгоритм состоит в повторяющихся проходах по сортируемому массиву. На каждой итерации последовательно сравниваются соседние элементы, и, если порядок в паре неверный, то элементы меняют местами. За каждый проход по массиву как минимум один элемент встает на свое место, поэтому необходимо совершить не более проходов, где размер массива, чтобы отсортировать массив.

Ниже приведен псевдокод сортировки пузырьком, на вход которой подается массив .

        public static void Bubble(ref int[] array) //сортировка пузырьком
        {
            var len = array.Length;
            for (var i = 1; i < len; i++)
            {
                for (var j = 0; j < len - i; j++)
                {
                    if (array[j] > array[j + 1])
                    {
                        Swap(ref array[j], ref array[j + 1]);
                    }
                }
            }

        }

10 -> 2000 Случайные числа

10 -> 2000 Реальные

Shaker

public static void Shaker(ref int[] array) //сортировка перемешиванием
        {
            for (var i = 0; i < array.Length / 2; i++)
            {
                var swapFlag = false;
                //проход слева направо
                for (var j = i; j < array.Length - i - 1; j++)
                {
                    if (array[j] > array[j + 1])
                    {
                        Swap(ref array[j], ref array[j + 1]);
                        swapFlag = true;
                    }
                }

                //проход справа налево
                for (var j = array.Length - 2 - i; j > i; j--)
                {
                    if (array[j - 1] > array[j])
                    {
                        Swap(ref array[j - 1], ref array[j]);
                        swapFlag = true;
                    }
                }

                //если обменов не было выходим
                if (!swapFlag)
                {
                    break;
                }
            }

        }

10 -> 2000 Synthetic

10 -> 10000 Real

Insertion

Задача заключается в следующем: есть часть массива, которая уже отсортирована, и требуется вставить остальные элементы массива в отсортированную часть, сохранив при этом упорядоченность. Для этого на каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированной части массива, до тех пор пока весь набор входных данных не будет отсортирован. Метод выбора очередного элемента из исходного массива произволен, однако обычно (и с целью получения устойчивого алгоритма сортировки), элементы вставляются по порядку их появления во входном массиве.

        public static void Insertion(ref int[] array) //сортировка вставками
        {
            int n = array.Length;
            for (int i = 1; i < n; ++i)
            {
                int key = array[i];
                int j = i - 1;

                // Move elements of arr[0..i-1],
                // that are greater than key,
                // to one position ahead of
                // their current position
                while (j >= 0 && array[j] > key)
                {
                    array[j + 1] = array[j];
                    j = j - 1;
                }
                array[j + 1] = key;
            }
        }

10 -> 2000 Synthetic

10 -> 10000 Real

Stooge

Рекурсивный алгоритм сортировки. Время работы алгоритма, таким образом, крайне большое по сравнению с эффективными алгоритмами сортировки

Aлгоритм сортировки списка элементов заключается в следующем:

Если значение элемента в конце списка меньше, чем значение элемента в начале, то поменять их местами.
Если есть 3 или более элементов в текущем подмножестве списка, то:
- Рекурсивно вызвать Stooge sort для первых 2/3 списка
- Рекурсивно вызвать Stooge sort для последних 2/3 списка
- Рекурсивно вызвать Stooge sort для первых 2/3 списка снова
Иначе: return

        public static void Stooge(ref int[] array, int startIndex, int endIndex) //сортировка по частям
        {
            if (array[startIndex] > array[endIndex])
            {
                Swap(ref array[startIndex], ref array[endIndex]);
            }

            if (endIndex - startIndex > 1)
            {
                var len = (endIndex - startIndex + 1) / 3;
                Stooge(ref array, startIndex, endIndex - len);
                Stooge(ref array, startIndex + len, endIndex);
                Stooge(ref array, startIndex, endIndex - len);
            }

        }
        public static void Stooge(ref int[] array) //сортировка по частям
        {
            Stooge(ref array, 0, array.Length - 1);
        }

10 -> 1000 Synthetic

10 -> 1000 Real

Pancake

Единственная операция, допустимая в алгоритме — переворот элементов последовательности до какого-либо индекса. В отличие от традиционных алгоритмов, в которых минимизируют количество сравнений, в блинной сортировке требуется сделать как можно меньше переворотов. Процесс можно визуально представить как стопку блинов, которую тасуют путём взятия нескольких блинов сверху и их переворачивания

        public static void Pancake(ref int[] array) //блинная сортировка
        {
            for (var subArrayLength = array.Length - 1; subArrayLength >= 0; subArrayLength--)
            {
                //получаем позицию максимального элемента подмассива
                var indexOfMax = IndexOfMax(array, subArrayLength);
                if (indexOfMax != subArrayLength)
                {
                    //переворот массива до индекса максимального элемента
                    //максимальный элемент подмассива расположится вначале
                    Flip(array, indexOfMax);
                    //переворот всего подмассива
                    Flip(array, subArrayLength);
                }
            }

        }

10 -> 2000 Synthetic

10 -> 2000 Real

Shell

Каждый проход в алгоритме характеризуется смещением $h_{i}$ , таким, что сортируются элементы отстающие друг от друга на $h_{i}$ позиций. Шелл предлагал использовать $h_{i}=N/2, h_{t-1}=h_{t}/2, …… , h_{0}=1$ Возможны и другие смещения, но $h_{i} =1$ всегда.

Начало.
Шаг 0. .
Шаг 1. Разобьем массив на списки элементов, отстающих друг от друга на $h_{i}$ Таких списков будет $h_{i}$
Шаг 2. Отсортируем элементы каждого списка сортировкой вставками.
Шаг 3. Объединим списки обратно в массив. Уменьшим . Если неотрицательно — вернемся к шагу 1
Конец.

        public static void Shell(ref int[] array) //сортировки Шелла
        {
            //расстояние между элементами, которые сравниваются
            var d = array.Length / 2;
            while (d >= 1)
            {
                for (var i = d; i < array.Length; i++)
                {
                    var j = i;
                    while ((j >= d) && (array[j - d] > array[j]))
                    {
                        Swap(ref array[j], ref array[j - d]);
                        j = j - d;
                    }
                }

                d = d / 2;
            }

        }

10 -> 10000 Synthetic

10 -> 10000 Real

Merge

Алгоритм использует принцип «разделяй и властвуй»: задача разбивается на подзадачи меньшего размера, которые решаются по отдельности, после чего их решения комбинируются для получения решения исходной задачи. Конкретно процедуру сортировки слиянием можно описать следующим образом:

Если в рассматриваемом массиве один элемент, то он уже отсортирован — алгоритм завершает работу.
Иначе массив разбивается на две части, которые сортируются рекурсивно.
После сортировки двух частей массива к ним применяется процедура слияния, которая по двум отсортированным частям получает исходный отсортированный массив.

        private static void merge(int[] arr, int l, int m, int r)
        {
            // original array is broken in two parts  
            // left and right array  
            int len1 = m - l + 1, len2 = r - m;
            int[] left = new int[len1];
            int[] right = new int[len2];

            for (int x = 0; x < len1; x++)
                left[x] = arr[l + x];

            for (int x = 0; x < len2; x++)
                right[x] = arr[m + 1 + x];

            int i = 0;
            int j = 0;
            int k = l;

            // after comparing, we merge those two array  
            // in larger sub array  
            while (i < len1 && j < len2)
            {
                if (left[i] <= right[j])
                {
                    arr[k] = left[i];
                    i++;
                }
                else
                {
                    arr[k] = right[j];
                    j++;
                }
                k++;
            }

            // copy remaining elements of left, if any  
            while (i < len1)
            {
                arr[k] = left[i];
                k++;
                i++;
            }

            // copy remaining element of right, if any  
            while (j < len2)
            {
                arr[k] = right[j];
                k++;
                j++;
            }
        }
        public static void Merge(ref int[] array) //сортировка слиянием
        {
            MergeSort(array, 0, array.Length - 1);
        }

10 -> 10000 Synthetic

10 -> 10000 Real

Selection

На каждом -ом шаге алгоритма находим -ый минимальный элемент и меняем его местами с -ым элементом в массиве. Таким образом будет получен массив, отсортированный по не убыванию.

        public static void Selection(ref int[] array, int currentIndex = 0) //сортировка выбором
        {
            if (currentIndex == array.Length)
                return;

            var index = IndexOfMin(array, currentIndex);
            if (index != currentIndex)
            {
                Swap(ref array[index], ref array[currentIndex]);
            }

             Selection(ref array, currentIndex + 1);
        }

10 -> 2000 Synthetic

10 -> 2000 Real

Quick

Быстрый метод сортировки функционирует по принципу "разделяй и властвуй".

Массив типа разбивается на два (возможно пустых) под массива и , таких, что каждый элемент меньше или равен , который в свою очередь, не превышает любой элемент под массива . Индекс вычисляется в ходе процедуры разбиения.
Под массивы и сортируются с помощью рекурсивного вызова процедуры быстрой сортировки.
Поскольку под массивы сортируются на месте, для их объединения не требуются никакие действия: весь массив оказывается отсортированным.

        static int[] QuickSort(int[] array, int minIndex, int maxIndex) //быстрая сортировка
        {
            if (minIndex >= maxIndex)
            {
                return array;
            }

            var pivotIndex = Partition(array, minIndex, maxIndex);
            QuickSort(array, minIndex, pivotIndex - 1);
            QuickSort(array, pivotIndex + 1, maxIndex);

            return array;
        }
        public static void Quick(ref int[] array) //сортировка Хоара
        {
            QuickSort(array, 0, array.Length - 1);
        }

10 -> 2000 Synthetic

10 -> 10000 Real

Gnome

Гномья сортировка основана на технике, используемой обычным голландским садовым гномом. Это метод, которым садовый гном сортирует линию цветочных горшков. По существу он смотрит на следующий и предыдущий садовые горшки: если они в правильном порядке, он шагает на один горшок вперёд, иначе он меняет их местами и шагает на один горшок назад. Граничные условия: если нет предыдущего горшка, он шагает вперёд; если нет следующего горшка, он закончил.

        public static void Gnome(ref int[] unsortedArray) //Гномья сортировка
        {
            var index = 1;
            var nextIndex = index + 1;

            while (index < unsortedArray.Length)
            {
                if (unsortedArray[index - 1] < unsortedArray[index])
                {
                    index = nextIndex;
                    nextIndex++;
                }
                else
                {
                    Swap(ref unsortedArray[index - 1], ref unsortedArray[index]);
                    index--;
                    if (index == 0)
                    {
                        index = nextIndex;
                        nextIndex++;
                    }
                }
            }
        }

10 -> 2000 Synthetic

10 -> 10000 Real

Tree

универсальный алгоритм сортировки, заключающийся в построении двоичного дерева поиска по ключам массива (списка), с последующей сборкой результирующего массива путём обхода узлов построенного дерева в необходимом порядке следования ключей. Данная сортировка является оптимальной при получении данных путём непосредственного чтения из потока (например, файла, сокета или консоли).

Построение двоичного дерева.
Сборка результирующего массива путём обхода узлов в необходимом порядке следования ключей.

class TreeNode //простая реализация бинарного дерева
    {
        public TreeNode(int data)
        {
            Data = data;
        }
        public int Data { get; set; } //данные
        public TreeNode Left { get; set; } //левая ветка дерева
        public TreeNode Right { get; set; } //правая ветка дерева
        public void Insert(TreeNode node) //рекурсивное добавление узла в дерево
        {
            if (node.Data < Data)
            {
                if (Left == null)
                {
                    Left = node;
                }
                else
                {
                    Left.Insert(node);
                }
            }
            else
            {
                if (Right == null)
                {
                    Right = node;
                }
                else
                {
                    Right.Insert(node);
                }
            }
        }
        public int[] Transform(List<int> elements = null) //преобразование дерева в отсортированный массив
        {
            if (elements == null)
            {
                elements = new List<int>();
            }

            if (Left != null)
            {
                Left.Transform(elements);
            }

            elements.Add(Data);

            if (Right != null)
            {
                Right.Transform(elements);
            }

            return elements.ToArray();
        }
    }
        public static void Tree(ref int[] array) //метод для сортировки с помощью двоичного дерева
        {
            var treeNode = new TreeNode(array[0]);
            for (int i = 1; i < array.Length; i++)
            {
                treeNode.Insert(new TreeNode(array[i]));
            }

            array = treeNode.Transform();
        }

10 -> 2000 Synthetic

10 -> 2000 Real

Comb

Производятся неоднократные прогоны по массиву, при которых сравниваются пары элементов. Если они неотсортированно друг относительно друга - то производится обмен. В результате крупные элементы мигрируют в конец массива, а небольшие по значению - в начало.

public static void Comb(ref int[] array) //Сортировка расческой
        {
            var arrayLength = array.Length;
            var currentStep = arrayLength - 1;

            while (currentStep > 1)
            {
                for (int i = 0; i + currentStep < array.Length; i++)
                {
                    if (array[i] > array[i + currentStep])
                    {
                        Swap(ref array[i], ref array[i + currentStep]);
                    }
                }

                currentStep = GetNextStep(currentStep);
            }

            //сортировка пузырьком
            for (var i = 1; i < arrayLength; i++)
            {
                var swapFlag = false;
                for (var j = 0; j < arrayLength - i; j++)
                {
                    if (array[j] > array[j + 1])
                    {
                        Swap(ref array[j], ref array[j + 1]);
                        swapFlag = true;
                    }
                }

                if (!swapFlag)
                {
                    break;
                }
            }
        }

10 -> 10000 Synthetic

10 -> 10000 Real

BasicCounting

Алгоритм сортировки, в котором используется диапазон чисел сортируемого массива для подсчёта совпадающих элементов. Применение сортировки подсчётом целесообразно лишь тогда, когда сортируемые числа имеют (или их можно отобразить в) диапазон возможных значений, который достаточно мал по сравнению с сортируемым множеством, например, миллион натуральных чисел меньших 1000.

public static void BasicCounting(ref int[] array) //простой вариант сортировки подсчетом
        {
            int n = array.Length;
            int max = 0;
            for (int i = 0; i < n; i++)
            {
                if (max < array[i])
                {
                    max = array[i];
                }
            }

            int[] freq = new int[max + 1];
            for (int i = 0; i < max + 1; i++)
            {
                freq[i] = 0;
            }
            for (int i = 0; i < n; i++)
            {
                freq[array[i]]++;
            }

            for (int i = 0, j = 0; i <= max; i++)
            {
                while (freq[i] > 0)
                {
                    array[j] = i;
                    j++;
                    freq[i]--;
                }
            }
        }

10 -> 100000 Synthetic

10 -> 100000 Real

CombinedBubble

Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется перестановка элементов. Проходы по массиву повторяются раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При каждом проходе алгоритма по внутреннему циклу очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим «наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции, как пузырёк в воде — отсюда и название алгоритма).

public static void CombinedBubble(ref int[] array)
        {
            int length = array.Length;

            int temp = array[0];

            for (int i = 0; i < length; i++)
            {
                for (int j = i + 1; j < length; j++)
                {
                    if (array[i] > array[j])
                    {
                        temp = array[i];

                        array[i] = array[j];

                        array[j] = temp;
                    }
                }
            }
        }

10 -> 2000 Synthetic

10 -> 2000 Real

Heapify

Необходимо отсортировать массив , размером . Построим на базе этого массива за кучу для максимума. Так как максимальный элемент находится в корне, то если поменять его местами с , он встанет на своё место. Далее вызовем процедуру , предварительно уменьшив на 1. Она за просеет на нужное место и сформирует новую кучу (так как мы уменьшили её размер, то куча располагается с по , а элемент находится на своём месте). Повторим эту процедуру для новой кучи, только корень будет менять местами не с , а . Делая аналогичные действия, пока не станет равен 1, мы будем ставить наибольшее из оставшихся чисел в конец не отсортированной части. Очевидно, что таким образом, мы получим отсортированный массив.

        public static void Heapify(ref int[] array) // Heapify
        {
            for (int i = array.Length / 2 - 1; i >= 0; i--)
                Heapify(array, array.Length, i);

            for (int i = array.Length - 1; i >= 0; i--)
            {
                int temp = array[0];
                array[0] = array[i];
                array[i] = temp;
                Heapify(array, i, 0);
            }
        }

10 -> 10000 Synthetic

10 -> 10000 Real

Cocktail

Производится многократный прогон по массиву, соседние элементы сравниваются и, в случае необходимости, меняются местами. При достижении конца массива направление меняется на противоположное. Таким образом по очереди выталкиваются крупные и мелкие элементы массива в конец и начало структуры соответственно. Коктейльная сортировка ещё называется двухсторонней сортировкой простыми обменами. Есть аналогичная модификация и для сортировки выбором.

public static void Cocktail(ref int[] array) // cocktail
        {
            int start = 0;
            int end = array.Length - 1;
            int temp;
            bool swapped = true;

            while (swapped)
            {
                swapped = false;

                for (int i = 0; i < end; i++)
                {
                    if (array[i] > array[i + 1])
                    {
                        temp = array[i];
                        array[i] = array[i + 1];
                        array[i + 1] = temp;
                        swapped = true;
                    }
                }

                if (!swapped)
                {
                    break;
                }

                swapped = false;
                end -= 1;

                for (int i = end; i >= start; i--)
                {
                    if (array[i] > array[i + 1])
                    {
                        temp = array[i];
                        array[i] = array[i + 1];
                        array[i + 1] = temp;
                        swapped = true;
                    }
                }

                start += 1;
            }
        }

10 -> 2000 Synthetic

10 -> 10000 Real

OddEven

Производится многократный прогон по массиву, соседние элементы сравниваются и, в случае необходимости, меняются местами. В отличие от пузырьковой сортировки шаг по массиву равен двум, а не единице.

public static void OddEven(ref int[] array)
        {
            //Initialization
            int Flag = 0;
            int temp = 0;

            //Initialize flag =0 or f!=1
            while (Flag == 0)
            {

                /*Initialize Flag is 1
                When both if condiotion is false so the flag remain 1 
                and the while loop is terminate*/

                Flag = 1;

                //use Even Loop for comparing even idexes of an array 

                for (int i = 0; i < array.Length - 1; i += 2)
                {
                    /* Use if conditon for comparing adjacents elements
                   
                     if they are in wrong order than swap*/

                    if (array[i] > array[i + 1])
                    {

                        temp = array[i];
                        array[i] = array[i + 1];
                        array[i + 1] = temp;
                        //This Flag variable is always remain 0 when if condition is true
                        Flag = 0;
                    }
                }


                //use Odd Loop for comparing odd idexes of an array 
                for (int i = 1; i < array.Length - 1; i += 2)
                {

                    /* Use if conditon for comparing adjacents elements
                        if they are in wrong order than swap*/
                    if (array[i] > array[i + 1])
                    {
                        //This Flag variable is always remain 0 when if condition is true
                        temp = array[i];
                        array[i] = array[i + 1];
                        array[i + 1] = temp;
                        Flag = 0;
                    }
                }

            }
            //return sorted array

        } // OddEven

10 -> 2000 Synthetic

10 -> 2000 Real

Tim

гибридный алгоритм сортировки, сочетающий различные подходы.

Данный алгоритм является относительно новым и был придуман Тимом Петерсом. На массивах данных, которые содержат упорядоченные под массивы, алгоритм Тима Петерса показывает себя намного лучше других сортировок. В настоящее время Timsort является стандартной сортировкой в Python и GNU Octave, реализован в OpenJDK 7 и Android JDK 1.5.

Алгоритм Timsort состоит из нескольких частей:

Начало.
Шаг 1. Входной массив разделяется на подмассивы фиксированной длины, вычисляемой определённым образом.
Шаг 2. Каждый под массив сортируется сортировкой вставками, сортировкой пузырьком или любой другой устойчивой сортировкой.
Шаг 3. Отсортированные под массивы объединяются в один массив с помощью модифицированной сортировки слиянием.
Конец.

        public static void Tim(ref int[] array)
        {
            int RUN = 32;

            for (int i = 0; i < array.Length; i += RUN)
                insertionSort(array, i, Math.Min((i + 31), (array.Length - 1)));

            for (int size = RUN; size < array.Length; size = 2 * size)
            {
                for (int left = 0; left < array.Length; left += 2 * size)
                {
                    int mid = left + size - 1;
                    int right = Math.Min((left + 2 * size - 1), (array.Length - 1));

                    merge(array, left, mid, right);
                }
            }

        } // Tim

10 -> 20000 Synthetic

10 -> 20000 Real

Counting

Исходная последовательность чисел длины nn, а в конце отсортированная, хранится в массиве A. Также используется вспомогательный массив Cс индексами от 0 до , изначально заполняемый нулями.

Последовательно пройдём по массиву A и запишем в количество чисел, равных i.

Теперь достаточно пройти по массиву C и для каждого в массив A последовательно записать число раз.

public static void Counting(ref int[] array)
        {
            int min = 0;
            int max = 0;
            for (int i = 0; i < array.Length; i++)
            {
                if (array[i] < min)
                    min = array[i];
                if (array[i] > max)
                    max = array[i];
            }

            int[] count = new int[max - min + 1];
            int z = 0;

            for (int i = 0; i < count.Length; i++)
                count[i] = 0;

            for (int i = 0; i < array.Length; i++)
                count[array[i] - min]++;

            for (int i = min; i <= max; i++)
            {
                while (count[i - min]-- > 0)
                {
                    array[z] = i;
                    ++z;
                }
            }

        } // Counting

10 -> 50000 Synthetic

10 -> 50000 Real

Bucket

Для карманной сортировки нужно разбить элементы массива входных данных на k блоков (карманов, корзин). Далее каждый из таких блоков сортируется либо другой сортировкой, либо рекурсивно тем же методом разбиения. После сортировок внутри каждых блоков данные записываются в массив в порядке разбиения на блоки. При этом нужно учитывать, что данная сортировка работает только в том случае, если разбиение на блоки производится таким образом, чтобы элементы каждого следующего блока были больше предыдущего.

Карманная сортировка сильно деградирует при большом количестве мало отличных элементов (большинство элементов попадёт в одну корзину). Поэтому такой тип сортировки использовать, когда велика вероятность того, что числа редко повторяются (например, последовательность случайных чисел).

 public static void Bucket(ref int[] array)
        {
            int minValue = array[0];
            int maxValue = array[0];

            for (int i = 1; i < array.Length; i++)
            {
                if (array[i] > maxValue)
                    maxValue = array[i];
                if (array[i] < minValue)
                    minValue = array[i];
            }

            List<int>[] bucket = new List<int>[maxValue - minValue + 1];

            for (int i = 0; i < bucket.Length; i++)
            {
                bucket[i] = new List<int>();
            }

            for (int i = 0; i < array.Length; i++)
            {
                bucket[array[i] - minValue].Add(array[i]);
            }

            int k = 0;
            for (int i = 0; i < bucket.Length; i++)
            {
                if (bucket[i].Count > 0)
                {
                    for (int j = 0; j < bucket[i].Count; j++)
                    {
                        array[k] = bucket[i][j];
                        k++;
                    }
                }
            }

        } // Bucket

10 -> 10000 Synthetic

10 -> 10000 Real

BinaryInsertion

Двоичная сортировка вставками — это алгоритм сортировки, похожий на сортировку вставками , но вместо использования линейного поиска для поиска места, куда должен быть вставлен элемент, мы используем двоичный поиск . Таким образом, мы уменьшаем сравнительную ценность вставки одного элемента с O (N) до O (log N).

        public static void BinaryInsertion(ref int[] array)
        {
            int count = 0;
            for (int i = 0; i < array.Length; i++)
            {
                int tmp = array[i]; int left = 0; int right = i - 1;
                while (left <= right)
                {
                    int m = (left + right) / 2; //определение индекса среднего элемента
                    if (tmp < array[m])
                        right = m - 1; // сдвиг правой
                    else left = m + 1; //или левой границы
                    count++;
                }

                for (int j = i - 1; j >= left; j--)
                {
                    array[j + 1] = array[j]; // сдвиг элементов
                                         // count++;
                }

                array[left] = tmp; // вставка элемента на нужное место
            }
        } // BinaryInsertion

10 -> 5000 Synthetic

10 -> 10000 Real

Bogo

Неэффективный алгоритм сортировки, используемый только в образовательных целях и противопоставляемый другим, более реалистичным алгоритмам. Если bogosort использовать для сортировки колоды карт, то сначала в алгоритме нужно проверить, лежат ли все карты по порядку, и если не лежат, то случайным образом перемешать её, проверить лежат ли теперь все карты по порядку, и повторять процесс, пока не от сортируется колода.

        public static void Bogo(ref int[] array)
        {
            while (!sorted(array))
            {
                Random rdm = new Random();
                for (int i = 0; i < array.Length; i++)
                {
                    {

                        for (int u = 0; u < array.Length; u++)
                        {
                            SwapBogo(ref array, u, rdm.Next(0, array.Length - 1));
                        }
                    }
                }

            }

        } // Bogo

Cycle

Это нестабильный алгоритм сортировки на месте, сортировка сравнением , которая теоретически оптимальна с точки зрения общего количества операций записи в исходный массив , в отличие от любого другого алгоритма сортировки на месте. Он основан на идее, что сортируемая перестановка может быть разбита на циклы , которые можно вращать по отдельности, чтобы получить отсортированный результат.

        public static void Cycle(ref int[] array)
        {
            for (int i = 0; i < array.Length - 1; i++)
            {
                int item = array[i];
                int pos = i;
                for (int j = i + 1; j < array.Length; j++)
                {
                    if (array[j] < item)
                    {
                        pos++;
                    }
                }
                if (pos == i)
                {
                    continue;
                }
                while (item == array[pos])
                {
                    pos++;
                }
                int var = item;
                item = array[pos];
                array[pos] = var;
                while (pos != i)
                {
                    pos = i;
                    for (int j = i + 1; j < array.Length; j++)
                    {
                        if (array[j] < item)
                        {
                            pos++;
                        }
                    }
                    while (item == array[pos])
                    {
                        pos++;
                    }
                    int temp = item;
                    item = array[pos];
                    array[pos] = temp;
                }
            }

        } // Cycle

10 -> 3000 Synthetic

10 -> 3000 Real

Exchange

Алгоритм сортировки обменом — это алгоритм, который сравнивает соседние элементы и перемещает их в правильное положение, меняя их местами на основе правила «меньше». Например, при сортировке по возрастанию мы могли бы поменять местами, если элемент слева больше, чем элемент справа. Итеративное выполнение этого процесса дает нам окончательный список, в котором входные элементы отсортированы в порядке возрастания.

        public static void Exchange(ref int[] array)
        {
            for (int i = 0; i < array.Length; i++)
            {
                for (int j = i; j < array.Length; j++)
                {
                    if (array[j] < array[i])
                    {
                        int container = array[j];
                        array[j] = array[i];
                        array[i] = container;
                    }
                }
            }

        } // Exchange

10 -> 3000 Synthetic

10 -> 3000 Real

Heap

Сортировка пирамидой использует бинарное сортирующее дерево. Сортирующее дерево — это такое дерево, у которого выполнены условия:

Каждый лист имеет глубину либо d, либо , максимальная глубина дерева.
Значение в любой вершине не меньше (другой вариант — не больше) значения её потомков .

        public static void Heap(ref int[] array)
        {
            int n = array.Length;


            for (int i = n / 2 - 1; i >= 0; i--)
                Heapify(array, n, i);

            for (int i = n - 1; i > 0; i--)
            {

                int temp = array[0];
                array[0] = array[i];
                array[i] = temp;

                Heapify(array, i, 0);
            }

        } // Heap

10 -> 10000 Synthetic

10 -> 10000 Real

MSDRadix

Исходно предназначен для сортировки целых чисел, записанных цифрами. Но так как в памяти компьютеров любая информация записывается целыми числами, алгоритм пригоден для сортировки любых объектов, запись которых можно поделить на «разряды», содержащие сравнимые значения. Например, так сортировать можно не только числа, записанные в виде набора цифр, но и строки, являющиеся набором символов, и вообще произвольные значения в памяти, представленные в виде набора байт.

public static void MSDRadix(ref int[] array) => MSDRadix(array, 0, array.Length - 1, 0, new int[array.Length]); // MSDRadix
private static int[] MSDRadix(int[] array, int l, int r, int d, int[] temp)
        {
            if (l >= r)
            {
                return new int[0];
            }

            const int k = 256;

            var count = new int[k + 2];
            for (var i = l; i <= r; i++)
            {
                var j = Key(array[i]);
                count[j + 2]++;
            }

            for (var i = 1; i < count.Length; i++)
            {
                count[i] += count[i - 1];
            }

            for (var i = l; i <= r; i++)
            {
                var j = Key(array[i]);
                temp[count[j + 1]++] = array[i];
            }

            for (var i = l; i <= r; i++)
            {
                array[i] = temp[i - l];
            }

            for (var i = 0; i < k; i++)
            {
                MSDRadix(array, l + count[i], l + count[i + 1] - 1, d + 1, temp);
            }

            int Key(int s) => d >= s ? -1 : s;

            return array;
        }

10 -> 200 Synthetic

10 -> 100 Real

Для справки Synthetic это данные сформированные функцией рандом в c#, Real это данные сгенерированные как нисходящая прямая с добавлением большого числа шума и выбросов.

Тесть алгоритмов производился на чистом Windows 10 так как в реальных условиях алгоритмы не будут работать на машинах реального времени, а будут использоваться в программах устанавливаемые пользователями на свои обычные компьютеры.

Если кому понадобиться код.

Интересный факт что алгоритм BasicCounting вышел куда быстрее чем стандартный алгоритм сортировки в C#.

График красного цвета "Array.Sort".
График черным цветом «BasicCounting».

P.s. Эта статья может понадобится школьником которым интересно какие существуют алгоритмы сортировок и примерные их характеристики.

P.s.s Это моя первая статья, тестовая. Так что не будьте строги. Заранее благодарю.

Источник: https://habr.com/ru/post/689738/

Вернуться к списку

Интересные статьи

Вычисляем на видеокартах. Технология OpenCL. Часть 2. Алгоритмы в условиях массового параллелизма

Автор курса «Разработчик C++» в Яндекс.Практикуме Георгий Осипов провёл вебинар «Вычисляем на видеокартах. Технология OpenCL». Мы подготовили для вас его текстовую версию, для удобства разбив е...

Настраиваем площадку Битрикс правильно: простые советы для сохранения душевного здоровья тимлида

Настройка любой площадки для CMS — это рутинный процесс, который должен быть доведен до автоматизма в каждой уважающей себя компании. А потому частенько воспринимается, как восход солнца — это происхо...

Производительность: нюансы против очевидностей

Приветствую, это текстовая версия моего доклада на JPoint-2021. Как обычно я сделал упор на случаи из жизни и на повседневные вещи, используемые каждым разработчиком. Под кат приглаш...

Кейс: Автосервис. Разработка рекламных кампаний и внедрение Битрикс24

История сегодня пойдёт про автосервис в Москве и его продвижении в течении 8 месяцев. Первое знакомство было ещё пару лет назад при странных обстоятельствах. Пришёл автосервис за заявками,...

«1С-Битрикс» предлагает продавать по-новому

В «1С-Битрикс» считают: современный интернет-магазин должен быть визуально привлекательным, адаптированным для просмотра с мобильных устройств и максимально персонализированным с помощью технологии Бо...