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

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

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

23.09.2022 00:38

mIka01 22 15000 Источник

Вступление

Здравствуйте, давно читаю Хабр и все хотел написать кому-нибудь статью, но не знал с чего начать и о чем писать. Но решил, что тянуть кота за причинное место. Надо просто взять и написать обзор о чем то что я знаю и что будет просто для начала. Поэтому решил описать алгоритмы сортировки в размере 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(n^{\frac{a^{log 3}}{log 1.5}})$	$O(n^{\frac{a^{log 3}}{log 1.5}})$	$O(n^{\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 log(n))$	$O(n\times log(n))$	$O(n\times log(n))$
Selection	$O(n^{2})$	$O(n^{2})$	$O(n^{2})$
Quick	$O(n\times log(n))$	$O(n\times log(n))$	$O(n^{2})$
Gnome		$O(n^{2})$	$O(n^{2})$
Tree		$O(n\times log(n))$	$O(n\times log(n))$
Comb		$O(\frac{n^2}{2^p})$	$O(n^{2})$
BasicCounting
CombinedBubble		$O(n^{2})$	$O(n^{2})$
Heapify	$O(n\times log(n))$	$O(n\times log(n))$	$O(n\times log(n))$
Cocktail		$O(n^{2})$	$O(n^{2})$
OddEven		$O(n^{2})$	$O(n^{2})$
Tim		$O(n\times log(n))$	$O(n\times log(n))$
Counting
Radix			$O(n\times k)$
Bucket	$O(n^{2})$	$O(n\times k)$
BinaryInsertion		$O(n\times log(n))$	$O(n\times log(n))$
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 log(n))$	$O(n\times log(n))$	$O(n\times log(n))$
MSDRadix	$O(n\times k)$	$O(n\times k)$	$O(n\times log(n))$

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

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 Это моя первая статья, тестовая. Так что не будьте строги. Заранее благодарю.

Комментарии (22)

ivanstor
23.09.2022 02:36
#24759670
+2
С виду добротно, хотя я только пролистал. Может быть ошибки и есть . Только вот предпоследний абзац было бы лучше поставить первым :-).
1. Aleshonne
  23.09.2022 18:59
  #24762044
  +3
  Как минимум для блуждающей сортировки (stooge sort) неправильно указана сложность. Должно быть a^(log_1.5(3)) = a^(ln(3)/ln(1.5)), а написано (a^ln(3))/ln(1.5). Мне сразу в глаза бросился константный множитель в O-нотации.

orbion
23.09.2022 02:46
#24759674
Быстрая, экономная, устойчивая...

Ещё есть экзотика вроде сортировки Хэна с асимптотикой N × log(log(N)), но её практически не используют из-за большого скрытого коэффициента.

А вообще у @valemakесть много интересных статей по самым разным сортировкам :)
1. orbion
  23.09.2022 03:28
  #24759692
  Оказывается, существует также сортировка Хэна для вещественных чисел с асимптотикой N × sqrt(log(N)) по времени и памяти

sashocq
23.09.2022 06:59
#24759760
Задел хороший, но статья качеством похожа больше на черновик.

Исправьте, пожалуйста, грамматические ошибки. Ооочень бросаются в глаза при чтении. Кажется, их прям много (в первых 3-х предложениях уже).

И что это за графики? Что за величины у них по осям X и Y? В каких единицах?
1. pfg21
  23.09.2022 09:52
  #24760020
  я бы еще добавил к графикам наложение функции сложности
  или общий график для сравнения сложности разных алгоритмов.
  соглашусь статью стоит еще расширять и дополнять.

Akina
23.09.2022 07:52
#24759810
+4
Считаю совершенно обязательным хотя бы в "Списке алгоритмов" добавить наиболее принятое/популярное наименование метода на русском языке. А лучше - все "устоявшиеся" наименования метода - как ихнеязычные, так и русскоязычные.

a-tk
23.09.2022 08:36
#24759866
+3
Столбец "Память" надо как-то развить: это память чего? Промежуточный буфер? Стек вызовов? Откуда для сортировок с обменом на месте там O(n)?
1. thevlad
  23.09.2022 14:48
  #24761072
  +1
  Там отдельный столбец надо, может ли сортировка в inplace или нет, или указывать асимптотику дополнительной памяти.

wataru
23.09.2022 11:27
#24760288
Что за a и k в таблице?
У Radix худшее время написанно O(n), а лучшее O(n x k), что выгляит больше. Т.е. в худшем случае сортировка получается быстрее чем в лучшем? Та же проблема в Counting.

Еще, этот k, похоже, разный в разных строчках. Так в Radix это должно быть количество разрядов в максимальном числе, когда как в Counting — это само максимальное число. Еще

Gryphon88
23.09.2022 12:10
#24760408
К это самое интересное. Ну и моменты «данные перестали влезать в кэш», «данные перестали влезать на страницу памяти», «перестали влезать в оперативку». Или частично отсортированные данные, которые встречаются очень часто.
1. a-tk
  23.09.2022 12:58
  #24760622
  Это всё-таки другая тема уже, ортогональная обозначенной.
  
  На эту тему посмотрите доклад https://www.youtube.com/watch?v=XGtieBVI1lk&ab_channel=DotNext
  
  Ну и другие доклады этого же товарища.

Siegurd1
23.09.2022 14:40
#24760920
+2
Оси на графиках нужно подписывать.

klimkinMD
23.09.2022 14:41
#24760940
Не встретил упоминания АВЛ деревьев -- расстроился.

rqdkmndh
23.09.2022 16:09
#24761596
Спасибо, хорошая подборка в одном месте. На мой взгляд, не хватает информации о применимости в том или ином случае.

PNSpasskiy
23.09.2022 19:16
#24762082
Спасибо. Отличная подборка.

p07a1330
23.09.2022 22:08
#24762452
Забыли Bozo сорт, сортировку перестановками (Perm sort) и сортировку Бабушкина :)

ibKpoxa
23.09.2022 23:03
#24762598
Академически у алгоритмов сортировки не производительность, а сложность, что было бы более корректным.

Даже в алгоритме пузырька сложность для идеального случая указана не корректно, ведь в псевдокоде просто пузырёк, а не оптимизированная версия. в некоторых других тоже, надо бы исправить.

logn это не выглядит как log(n), не красиво, тоже просьба исправить. Про память коллеги это упомянули.

Для курсовика на 1 курсе покатит, у меня был аналогичный в то время :)

Daddy_Cool
24.09.2022 01:52
#24762838
+1
Автор проделал большую работу. Так а вывод-то какой?
Я хочу сортировать... какой алгоритм мне использовать? Я так понимаю, есть следующие пользовательские условия/требования/ограничения.
1. Количество элементов, на 100 элементах выгоднее один алгоритм, на 100 млн - другой.
2. Возможность параллелизации. (Видеокарты у всех же нынче простаивают).
3. Объем памяти - он есть в таблице, дают ли алгоритмы требующие больше памяти существенный выигрыш во времени?
1. baklajan
  24.09.2022 06:56
  #24762932
  +1, хотелось бы увидеть итоговую таблицу, с выводами на 10, 50, 100, 500, 1000, 5000, 10000.
  На каких количествах какие алгоритмы лучшие? Какие самые универсальные?
  Но все равно спасибо за проделанную работу.

VMarkelov
25.09.2022 01:53
#24764664
Спасибо за труд! К уже сказанному выше про подпись осей графиком и какие-то общие выводы, есть и мои собственные замечания:
1. Хотелось бы описания поуникальнее или поподробнее. С пояснением, чем же конкретная сортировка знаменита и какова область её использования. Сами сравните описание Bubble и Comb. По описанию Comb я вообще не понимаю в чём её плюс и отличие по сравнению с Bubble - слова одни и те же. Да, можно почитать код и разобрать его. Но в таком случае, какой смысл описаний? Ещё пример:Coctail против Shaker - про оба написано, что каждый проход меняется порядок. А в чём их особенности? Почему они по разному названы?
2. Местами текст выглядит неоконченным или просто неясно сформулированным. Вот возьмем последнюю строку из первого абзаца про Shell:
  Шелл предлагал использовать $h_{i}=N/2, h_{t-1}=h_{t}/2, …… , h_{0}=1$ Возможны и другие смещения, но $h_{i} =1$ всегда.
  Почему "Hi = 1 всегда?" Что это значит?
3. Все сортировки выглядя полезными и применимыми в разных ситуациях. Даже пузырьковая. Но что в этом списке делает bogosort? Если уж впихивать совершенно неэффективные алгоритмы, которые написаны чисто для прикола, то их, во-первых, больше чем одна, во-вторых, по моему мнению, им место в отдельном посте с описанием других "не от мира сего" сортировок.

TotalAMD
25.09.2022 05:55
#24764758
+1
Что за графики без подписей?! ????