Дурацкая сортировка

«Дурацкая сортировка», она же «stupid sort» ― относится к классу «сортировок обменом». Сложность сортировки в лучшем, среднем и худшем случае [math]O(n^{3})[/math] (постоянство ― признак мастерства ). Просматривается массив, начиная с первого элемента, по пути сравниваются соседние элементы. Если находят неотсортированную пару ― элементы меняются местами, происходит возврат в начало массива и всё повторяется. Процесс заканчивается, если добрались до последнего элемента массива.

В аттаче asm-/rc-/exe-файлы и курсор

 

Придурковатая сортировка

Она же «сортировка по частям», она же «блуждающая сортировка» ― относится к классу «сортировок обменом». Сложность сортировки в лучшем, среднем и худшем случае [math]O(n^{\frac{\displaystyle log_{2}(3)}{\displaystyle log_{2}(1,5)}})\approx O(n^{2,70951})[/math]. Сортировка названа в честь американской комик-группы «Three stooges» («Три придурка»). Коллектив трио периодически менялся. В алгоритм заложен элемент абсурда ― обычно массив давно отсортирован, но сортировка продолжает безумно метаться по третям массива.

• Сравнивают элементы в начале и конце подмассива (первоначально это весь массив).
• Если значение элемента в начале массива больше чем у элемента в конце массива, тогда элементы меняют местами.
• Рекурсивно применяют сортировку для первых 2/3 элементов массива.
• Рекурсивно применяют сортировку для последних 2/3 элементов массива.
• Снова рекурсивно применяют сортировку для первых 2/3 элементов массива

В аттаче asm-/rc-/exe-файлы и курсор

 

Сортировка подсчетом

Она же «Counting sort» ― относится к классу «сортировок подсчетом». Вычисляется значения максимального [math]max[/math] элемента массива. Выделяется вспомогательный массив [math]count[0...k][/math], заполненный нулями, где [math]k=max.[/math] Подсчитывается сколько раз в сортируемом массиве [math]A[/math] встречается каждое значение и для каждого [math]A[i][/math] увеличивается [math]count[A[i]][/math] на единицу. Проходят по массиву [math]count[/math], [math]j\in\{0,...,k\}[/math] в массив [math]A[/math] последовательно записывают число [math]j[/math] столько раз, сколько указано в ячейке [math]count[j].[/math] Сложность сортировки в лучшем случае [math]O(n)[/math], в среднем и худшем случае [math]O(n+k)[/math]

В аттаче asm-/rc-/exe-файлы и курсор

 

Цикличная сортировка
или семь раз отмерь (cmp) ― один отрежь (swap)

​

Она же «Cycle sort» ― относится к классу «сортировок выбором». Сложность сортировки в лучшем, среднем и худшем случае [math]O(n^{2})[/math]
Выбирается очередной элемент. Для него отыскивается подходящее место в массиве. Элемент помещается в найденное место, а элемент, который занимал нужное место, извлекается и новое расположение ищется теперь для него... Продолжаем, пока на найдем элемент, который нужно положить на место того, с которого начали. Круг замкнулся.
Циклы повторяются для каждого элемента массива слева направо.
На i-й итерации все элементы левее i-го уже стоят на своих местах. Анализировать нужно только тех, кто правее i-й позиции.
Чтобы определить правильное место, элемента, достаточно посчитать, сколько элементов меньше него (на сколько позиций правее он должен быть).
Большое количество сравнений обычно делает этот алгоритм не слишком эффективным. Его область применения ― задачи в которых велика «стоимость» записи в массив. Цикличная сортировка ценна тем, что изменения среди элементов массива происходят только в случаях, когда элемент ставится на своё место. Это важно, если перезапись в массиве обходится слишком «дорого» и актуальны минимальные изменения в физической памяти. Количество перестановок в этом алгоритме минимально.

В аттаче asm-/rc-/exe-файлы и курсор.

 

Гравитационная сортировка

Она же «сортировка бусинами», она же «сортировка абаком», она же «Bead Sort» ― относится к классу «сортировок распределением». Операции сравнения используются при поиске максимального элемента, чтобы потом выделить дополнительную память [math]max\times n[/math], где [math]n[/math] — количество элементов в массиве. Сложность по времени:

• [math]O(\sqrt {n})[/math], где [math]n[/math] — количество рядов — В реалистичной симуляции гравитации время, затрачиваемое на расчет падения бусин, прямо пропорционально квадратному корню из количества рядов.
• [math]O(n)[/math] — Бусины просчитываются по одному ряду за раз.
• [math]O(S)[/math], где [math]S[/math] — сумма всех чисел в изначальном массиве — Каждая бусина просчитывается индивидуально.

В аттаче asm-/rc-/exe-файлы и курсор

 

Сортировка деревом

Она же «сортировка с помощью бинарного дерева», она же «tree sort» — относится к классу «сортировок вставками». Алгоритм сортировки, заключающийся в построении двоичного дерева поиска. Первый элемент — корень дерева, остальные добавляются по следующему принципу — начиная с корня дерева, элемент сравнивается с узлами, если элемент меньше чем узел — тогда спускаемся по левой ветке, если не меньше — тогда по правой. Спустившись до конца, элемент сам становится узлом. Построенное таким образом дерево можно легко обойти так, чтобы двигаться от узлов с меньшими значениями к узлам с большими значениями. При этом получаем все элементы в возрастающем порядке. Сортировка является оптимальной при получении данных путем непосредственного чтения из потока (файла, сокета или консоли).
Процедура добавления [math]n[/math] объектов в бинарное дерево имеет среднюю алгоритмическую сложность порядка [math]O(n\cdot log_{2}(n))[/math], что относит сортировку к группе «быстрых сортировок». Cложность добавления одного объекта в разбалансированное дерево может достигать [math]O(n)[/math], что для [math]n[/math] элементов приведет к общей сложности порядка [math]O(n^{2})[/math]. Сложность сортировки в лучшем и среднем случае [math]O(n\cdot log_{2}(n))[/math], в худшем случае [math]O(n^{2})[/math]. Сложность сортировки по памяти [math]O(4\cdot n)[/math] — при развертывании древовидной структуры в памяти требуется не менее чем [math]4n[/math] ячеек дополнительной памяти (каждый узел должен содержать ссылки на элемент исходного массива, на родительский элемент, на левый и правый лист), существуют способы уменьшить требуемую дополнительную память.

В аттаче asm-/rc-/exe-файлы и курсор

 

Intro,
а с чем связано то, что для нормальной работы BitonicSort значение ArraySize должно быть 2^N? Заменой деления на сдвиги?

 

Битонная сортировка

«Битонная сортировка», она же «bitonic sort» ― относится к классу «параллельных сортировок». Сложность сортировки в лучшем, среднем и худшем случае [math]O(n\cdot log_{2}^{2}(n))[/math] Алгоритм основан на понятии битонных последовательностей и операций над ними. Битонной последовательностью называют последовательность, которая монотонно не убывает, а затем монотонно не возрастает.
Чтобы превратить любую битонную последовательность в отсортированную, нужно:

1. Разделить последовательность пополам, попарно сравнить элементы [math]x_{i}[/math] и [math]x_{\frac{n}{2}+i}[/math], меняя их местами, если элемент из первой половины больше (или меньше).
2. Рекурсивно выполнить эту сортировку над каждой из получившихся половин.

Чтобы превратить произвольную последовательность в битонную, нужно:

1. Разделить последовательность пополам.
2. Первую часть превратить в битонную последовательность и отсортировать по возрастанию.
3. Вторую часть превратить в битонную и отсортировать по убыванию.

Реализация

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

Временная сложность

Сортировка рекурсивно разбивается на [math]log_{2}(n)[/math] уровней. Каждый рекурсивный вызов уменьшает размер подмассива в 2 раза, при этом количество таких подмассивов в два раза увеличивается. Сначала сравниваются [math]\frac{n}{2}[/math] пар, затем[math]\frac{n}{4}[/math] в одной половине массива и [math]\frac{n}{4}[/math] в другой, и так далее...
[math]\frac{n}{2}+2\frac{n}{4}+4\frac{n}{8}+...=\frac{n}{2}\times log_{2}(n)[/math]
Общее количество сравнений равно [math]\frac{n}{2}log_{2}(n)[/math]

В аттаче asm-/rc-/exe-файлы и курсор

 

R81...,
но я же не Дональд Кнут А если серьезно, названия у каких сортировок нужно поправить, какие более правильные определения должны быть? Напишите, можно в личку, я поправлю