Битонная сортировка, версия 2.0

Переделал битонную сортировку
В аттаче asm-/rc-/exe-файлы и курсор

 

Поразрядная сортировка (Least Significant Digit)

Поразрядная сортировка (radix LSD sort) — алгоритм сортировки, который выполняется за линейное время ― относится к классу «сортировок распределением».
Двигаемся от младших разрядов к старшим и на каждой итерации распределяем элементы массива в зависимости от того, какая цифра содержится в разряде.
После очередного распределения возвращаем элементы в основной массив в том порядке, в котором элементы попали в классы при очередном перераспределении.

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

 

Оптимизированная гномья сортировка

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

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

 

		сложность по времени			сложность по памяти​
		лучшая	средняя	худшая	общая	допол- нительная​
1	Bubble Sort	[math]O(n)[/math]	[math]O(\frac{n\cdot(n-1)}{1,33})[/math]	[math]O(n^{2})[/math]	[math]O(n)[/math]	[math]O(1)[/math]
2	Optimized Bubble Sort​	[math]O(n)[/math]	[math]O(\frac{n\cdot(n-1)}{2,28})[/math]	[math]O(n^2)[/math]	[math]O(n)[/math]	[math]O(1)[/math]
3	Cocktail Sort	[math]O(n)[/math]	[math]O(n^2)[/math]	[math]O(n^2)[/math]
4	Optimized Cocktail Sort​
5	Odd-even sort	[math]O(n)[/math]	[math]O(n^2)[/math]	[math]O(n^2)[/math]	[math]O(n)[/math]	[math]O(1)[/math]
6	Gnom sort	[math]O(n)[/math]	[math]O(n^2)[/math]	[math]O(n^2)[/math]	[math]O(n)[/math]	[math]O(1)[/math]
7	Optimized Gnom sort​	[math]O(n)[/math]	[math]O(n^2)[/math]	[math]O(n^2)[/math]	[math]O(n)[/math]	[math]O(1)[/math]
8	Optmized Gnom sort Binary Seach​	[math]O(n)[/math]	[math]O(n^2)[/math]	[math]O(n^2)[/math]
9	Comb Sort	[math]O(\frac{n^2}{2^p})[/math]	[math]O(n)[/math]	[math]O(n^2)[/math]	[math]O(n)[/math]	[math]O(1)[/math]
10	Cycle sort	—	[math]O(n^{2})[/math]	[math]O(n^{2})[/math]	[math]O(n)[/math]	[math]O(1)[/math]
11	Quick Sort Left/ Left Pointers​	[math]O(n\cdot log_{2}(n))[/math]	[math]O(n\cdot log_{2}(n))[/math]	[math]O(n^{2})[/math]	[math]O(n)[/math]
12	Quick Sort Left/ Right Pointers​	[math]O(n\cdot log_{2}(n))[/math]	[math]O(n\cdot log_{2}(n))[/math]	[math]O(n^{2})[/math]	[math]O(n)[/math]
13	Dual-Pivot Quick Sort​	[math]O(n\cdot log_{2}(n))[/math]	[math]O(n\cdot log_{2}(n))[/math]	[math]O(n^{2})[/math]	[math]O(n)[/math]
14	Stable Quick Sort​	[math]O(n\cdot log_{2}(n))[/math]	[math]O(n\cdot log_{2}(n))[/math]	[math]O(n^{2})[/math]	[math]O(n)[/math]
15	Selection Sort​	[math]O(n^{2})[/math]	[math]O(n^{2})[/math]	[math]O(n^{2})[/math]
16	Double Selection Sort​	[math]O(n^{2})[/math]	[math]O(n^{2})[/math]	[math]O(n^{2})[/math]
17	Max Heap Sort	[math]O(n\cdot log_{2}(n))[/math]	[math]O(n\cdot log_{2}(n))[/math]	[math]O(n\cdot log_{2}(n))[/math]
18	Min Heap Sort	[math]O(n\cdot log_{2}(n))[/math]	[math]O(n\cdot log_{2}(n))[/math]	[math]O(n\cdot log_{2}(n))[/math]
19	Flipped Min Heap Sort​	[math]O(n\cdot log_{2}(n))[/math]	[math]O(n\cdot log_{2}(n))[/math]	[math]O(n\cdot log_{2}(n))[/math]
20	Weak Heap Sort	[math]O(n\cdot log_{2}(n))[/math]	[math]O(n\cdot log_{2}(n))[/math]	[math]O(n\cdot log_{2}(n))[/math]
21	Ternary Heap Sort​	[math]O(n\cdot log_{2}(n))[/math]	[math]O(n\cdot log_{2}(n))[/math]	[math]O(n\cdot log_{2}(n))[/math]
22	Smoothsort	[math]O(n)[/math]
23	Poplar Heap Sort​	[math]O(n\cdot log_{2}(n))[/math]	[math]O(n\cdot log_{2}(n))[/math]	[math]O(n\cdot log_{2}(n))[/math]
24	Tournament sort​	—
25	Insertion Sort​	[math]O(n)[/math]	[math]O(n^{2})[/math]	[math]O(n^{2})[/math]
26	Binary Insertion Sort​
27	Shell Sort	[math]O(n\cdot log_{2}(n))[/math]	[math]O(n\cdot log^{2}_{2}(n))[/math]	[math]O(n\cdot log^{2}_{2}(n))[/math]	[math]O(n)[/math]	[math]O(1)[/math]
28	Patience sorting​	[math]O(n)[/math]	[math]O(n\cdot log_{2}(n))[/math]	[math]O(n\cdot log_{2}(n))[/math]	[math]O(n^{2})[/math]
29	Unbalance Tree Sort​	[math]O(n\cdot log_{2}(n))[/math]	[math]O(n\cdot log_{2}(n))[/math]	[math]O(n^{2})[/math]	[math]O(n)[/math]
30	Merge sort	[math]O(n\cdot log_{2}(n))[/math]	[math]O(n\cdot log_{2}(n))[/math]	[math]O(n\cdot log_{2}(n))[/math]	[math]O(n)[/math]	[math]O(n)[/math]
31	Button-up Merge sort​	[math]O(n\cdot log_{2}(n))[/math]	[math]O(n\cdot log_{2}(n))[/math]	[math]O(n\cdot log_{2}(n))[/math]	[math]O(n)[/math]	[math]O(n)[/math]
32	In-Place Merge sort​	—	—	[math]O(n\cdot log^{2}_{2}(n))[/math]
33	Andrey Astrelin's In Place Merge Sort​
34	Lazy Stable Sort​
35	Rotate Merge Sort​
36	Counting Sort​	[math]O(n+k)[/math]	[math]O(n+k)[/math]	[math]O(n+k)[/math]
37	Pigeonhole Sort​
38	Gravity (Bead) Sort​
39	American Flag Sort​
40	Least Significant Digit Radix Sort​	[math]O(n\cdot k)[/math]	[math]O(n\cdot k)[/math]	[math]O(n^{2})[/math]
41	In-Place LSD Radix Sort​	[math]O(n\cdot k)[/math]	[math]O(n\cdot k)[/math]	[math]O(n^{2})[/math]
42	Most Significant Digit Radix Sort​
43	Flash Sort
44	Iterative Binary Quick Sort​
45	Recursive Binary Quick Sort​
46	Shatter Sort
47	Simple Shatter Sort​
48	Time Sort Mul 10​
49	Batcher's Bitonic Sort​
50	Batcher's Odd-Event Merge Sort​
51	Recursive Pairwise Sorting Network​
52	Iterative Bitonic Sort​
53	Iterative Odd-Even Merge Sort​
54	Iterative Pairwise Sorting Network​
55	Hybrid Comb Sort​
56	Introspective Circle Sort​
57	Binary Merge Sort​
58	Weave Merge Sort​
59	TimSort	[math]O(n)[/math]	[math]O(n\cdot log_{2}(n))[/math]	[math]O(n\cdot log_{2}(n))[/math]
60	Cocktail Merge Sort​
61	Wikisort
62	Grail Sort (Block Merge Sort)​
63	Sqrtsort
64	Introspective Sort (std::sort)​
65	Opimized Bottom-Up Merge Sort​
66	Opimized Dual-Pivot Quick Sort (Array Sort)​
67	Pattern- Defeating Quick Sort​
68	Branchless Pattern- Defeating Quick Sort​
69	Pancake Sort
70	Bad Sort
71	Stooge Sort
72	Silly Sort
73	Slow Sort
74	Exchange Bogo Sort​
75	Bubble Bogo Sort​
76	Less Bogo Sort
77	Cocktail Bogo Sort​
78	Bogo Bogo Sort​
79	Bogo Sort
80	Tree Sort	[math]O(n\cdot log_{2}(n))[/math]	[math]O(n\cdot log_{2}(n))[/math]	[math]O(n^{2})[/math]	[math]O(n)[/math]
81	Bucket Sort​	[math]O(n)[/math]	[math]O(n+k)[/math]	[math]O(n^2)[/math]	[math]O(n\cdot k)[/math]

 

Медленная сортировка

Она же «вялая сортировка», она же «Slow Sort» ― относится к классу «сортировок обменом». Сложность сортировки в лучшем, среднем и худшем случае [math]O(n^{\left(\frac{\displaystyle log_{2}(n)}{\displaystyle 2+\varepsilon}\right)})[/math]

1. Если массив состоит из одного элемента ― завершаем рекурсию.
2. Если массив состоит из двух и более элементов ― делим его пополам.
3. Применяем рекурсивно алгоритм к левой половине массива.
4. Применяем рекурсивно алгоритм к правой половине массива.
5. Сравниваются элементы на концах массива (и меняются при необходимости).
6. Рекурсивно применяем алгоритм к подмассиву без последнего элемента.

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

 

Оптимизированная пузырьковая сортировка

Упорядочивание происходит в результате обхода массива с конца в начало, по пути происходит обмен местами у неотсортированных соседних элементов. В результате первого прохода в начало массива «всплывет» минимальный элемент. Во время движения находим максимальный элемент и меняем его с тем элементом, который находится в конце массива. Снова обходим массив от предпоследнего элемента ко второму и меняем по пути неотсортированные соседние элементы. По сути получили сортировку шейкером, когда массив заполняется за один проход с противоположных сторон максимальными и минимальными элементами. Введение флажка обменов помогает уменьшить число проходов по массиву. Перед каждым проходом флажок сбрасывается в 0, а после произошедшего обмена устанавливается в 1. Если после выхода из внутреннего цикла флажок равен 0, это означает, что обменов не было ― массив отсортирован и можно досрочно завершить сортировку.

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

 

Intro,
у вас 3.ShakerSort и 15.CocktailSort, но ведь это одно и то же? И почему в CocktailSort каждый раз продолжается движение в самый конец к [math](n-1)[/math]-му элементу и в самое начало к [math]0[/math]-му элементу, ведь участки в начале и конце массива уже отсортированы? Получается, что ShakerSort это оптимизированная сортировка CocktailSort?

 

Оптимизированная шейкерная сортировка

Производятся многократные проходы по массиву, соседние элементы сравниваются и, в случае необходимости, меняются местами. При достижении конца массива направление меняется на противоположное. Первый проход ― движемся от [math]n[/math]-ого элемента к 1-му элементу. Во время движения в начало массива находим максимальный элемент и меняем его с [math]n[/math]-ым элементом, при этом минимальный элемент выталкивается на место 1-го элемента массива. Второй проход ― во время движения от 2-го элемента массива к ([math]n[/math]-1)-му элементу находим минимальный элемент и меняем его со 2-ым элементом. Одновременно, при движении по массиву, максимальный элемент выталкивается в ([math]n[/math]-1)-ый элемент массива. Таким образом во время одного прохода происходит заполнение максимальным и минимальным элементами конца и начала массива. Так как в начале и конце массива элементы полностью отсортированы, поэтому каждый раз проход от начального к конечному элементу становится на два элемента короче.

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

 

Сортировка Таноса

Она же «Русская сортировка половинами» (Russian sorting halves), она же «Thanos sort», она же «Средне-арифметическая ведерная сортировка» (Average bucket sort) ― относится к классу «сортировок распределением». Сложность сортировки в лучшем случае [math]O(n)[/math], в среднем ― [math]O(n+k)[/math], в худшем ― [math]O(n^{2})[/math]
В подмассиве (на первом шаге подмассивом является весь массив) вычисляется среднее арифметическое среди элементов. Затем элементы подмассива сравниваются со средним арифметическим и в зависимости от сравнения отправляются в левую или в правую часть подмассива. Затем те же действия рекурсивно производятся по отдельности с левой и с правой частью подмассива.

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

 

Корзиная сортировка с рекурсией

Она же «Bucket sort», она же «Карманная сортировка», она же «Ведерная сортировка», она же «Блочная сортировка» ― относится к классу «сортировок распределением». Сложность сортировки в лучшем случае [math]O(n)[/math], в среднем ― [math]O(n+k)[/math], в худшем ― [math]O(n^2)[/math]
Основная идея ― распределение элементов по корзинам (блокам, карманам, ведрам), то есть группировка элементов по определенному признаку. Элементы в каждой корзине группируем по уточняющим признакам. Процесс распределения продолжается, пока в каждой корзине не окажутся одинаковые элементы.
Для конкретной реализации в массиве отыскивались максимальный и минимальный элементы, затем массив делится на правый и левый подмассив, в которых значения элементов больше или меньше значения [math]\frac{max+min}{2}[/math]. Затем те же действия рекурсивно производятся по отдельности с левой и с правой частью подмассива. Хотя у нас появлялись максимальные и минимальные элементы, которые можно сразу ставить на положенное место в массиве, но это усложняло алгоритм и не давало никакого выигрыша.

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

 

Классическая сортировка корзинами

Относится к классу «сортировок распределением». Сложность сортировки в лучшем случае [math]O(n)[/math], в среднем ― [math]O(n+k)[/math], в худшем ― [math]O(n^2)[/math]
В массиве элементы со значениями от 1 до 511, то есть каждый элемент кодируется 9 разрядами (2⁹=512). Отведем под сортировку 128 корзин (2⁷=128). В корзине должно быть место под 4 элемента (2^9-7=4), но возможно, что часть корзин будет пустыми, а в части корзин будет более чем 4 элемента. Заводим массив из 128 счетчиков, обнуляем счетчики, пробегаемся по исходному массиву ― смотрим сколько элементов будет соответствовать 7-разрядному «ключу». Ищем в массиве счетчиков максимум. Выделяем память под корзины из расчета (128 корзин)×[math]max[/math]×(размер элемента в байтах). Заполняем корзины в соответствии с 7-разрядным «ключом», если место на «дне» корзины занято, тогда помещаем элемент в корзину на свободное место. Пробегаем по массиву счетчиков и перемещаем элементы из корзины в исходный массив. Если корзина пуста ― пропускаем ее, если в корзине более одного элемента ― сортируем элементы в корзине и отсортированные элементы отправляем в исходный массив.

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

 

таблица с названиями сортировок

упс 65434 байта, хотя должно быть байт 200 максимум. Ей богу! Эксперименты не проводил...