Сортировка Бабушкина :: 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) |
Алексей Бабушкин на Уютненьком