Сортировка Бабушкина :: Babushkin sort

Фейковый алгоритм сортировки, основанный на методе архивации файлов, предложенным алтайским студентом Алексеем Бабушкиным. Сам Бабушкин непосредственно автором алгоритма не является.

Метод Бабушкина архивации файлов

Алгоритм архивации таков: любой файл представляет собой HEX-последовательность символов, переводим этот HEX в DEC, получаем неебически-большое число, дописываем перед этим число 0, — получаем число в диапазоне от 0 до 1 с огромным числом знаков после запятой, а дальше всё просто — подбираем 2 таких целочисленных числа, частное которых даст нам искомое число в диапазоне от 0 до 1 с точностью совпадений до последнего знака. Беда в подборе чисел, которое может идти и 2 часа, а может идти и 2 недели. Есть опытные образцы и работающая программа, и всё это работает.

Алексей Бабушкин

Сортировка Бабушкина

Алгоритм

1) Допустим, нужно отсортировать массив из n элементов (индексация начинается с 0, индекс последнего элемента n — 1).
2) Специально подбираем два взаимно простых десятичных числа, x и y (x < y). 3) Делим x на y. Получаем дробное число от 0 до 1. Ноль отбрасываем, дробную часть оставляем. По сути дела получаем некое целое десятичное число. 4) DEC-представление числа, полученное на шаге 3, переводим в n-ричную систему счисления. 5) Берём в массиве 0-й элемент и помещаем его в дополнительный массив на позицию, индекс которой равен первой цифре в n-ричном представлении числа, полученном на шаге 4. 6) Берём в массиве 1-й элемент и помещаем его в дополнительный массив на позицию, индекс которой равен второй цифре в n-ричном представлении числа, полученном на шаге 4. 7) Берём в массиве 2-й элемент и помещаем его в дополнительный массив на позицию, индекс которой равен третьей цифре в n-ричном представлении числа, полученном на шаге 4. … n + 3) Берём в массиве (n - 2)-й элемент и помещаем его в дополнительный массив на позицию, индекс которой равен предпоследней цифре в n-ричном представлении числа полученном на шаге 4. n + 4) Берём в массиве (n - 1)-й элемент и помещаем его в дополнительный массив на позицию, индекс которой равен последней цифре в n-ричном представлении числа полученном на шаге 4. n + 5) Переносим все элементы из дополнительного массива в основной.

Характеристики алгоритма

Название Сортировка Бабушкина (Babushkin sort)
Автор Алексей Бабушкин
Год 2013
Класс Эзотерические сортировки
Устойчивость Да
Сравнения Нет
Сложность по времени Худшая O(n)
Средняя
Лучшая
Сложность по памяти Дополнительная O(n)

Ссылки

Хабрахабр: Непрактичные сортировки – бессмысленные и беспощадные

Алексей Бабушкин на Луркоморье

Добавить комментарий