А что это мы всё об умных да об эффективных алгоритмах? А давайте эту тоскливую осеннюю пятницу развеем чем-нибудь контрпродуктивным!?
Представляю Вашему вниманию ТОП-5 самых нетрадиционных сортировок всех времён и народов.
Младопрограммистам такое полезно показывать в дидактических целях. Всех остальных как минимум позабавит.
Болотная сортировка (BogoSort)
С этой сортировкой нужно быть предельно осторожным. Неосмотрительно угодив в трясину, рискуете сгинуть навсегда.
Принцип прост как плесень. Перетряхиваем массив до тех пор пока он внезапно не отсортируется. Процесс может счастливо завершиться сразу, а может длиться до тепловой смерти Вселенной. Это уж как повезёт.
Средняя сложность по времени: O(n x n!). Есть также и лучшая: Ω(n). Что интересно, худшая временная сложность этого алгоритма науке неизвестна.
import java.util.Random;
public class BogoSortAlgorithm extends SortAlgorithm {
//Если есть массив, значит его можно отсортировать
public void sort(int data[]) throws Exception {
if (data.length > 0) runBogoSort(data);
}
//А вот и сортировочное болото
private void runBogoSort(int data[]) throws Exception {
Random generator;
int tempVariable;
int randomPosition;
do {
generator = new Random();
for (int i = 0; i < data.length; i++) {
randomPosition = generator.nextInt(data.length);
tempVariable = data[i];
data[i] = data[randomPosition];
data[randomPosition] = tempVariable;
pause(i,randomPosition);
}
} while(!isSorted(data)); //Пока не отсортируем
}
//Проверяем, отсортирован ли массив
private boolean isSorted(int data[]) {
for (int i = 1; i < data.length; i++)
if (data[i] < data[i - 1]) return false;
return true;
}
}
Сортировка клоуна Бозо (BozoSort)
Где BogoSort, там и BozoSort. Метод сортировки детского клоуна Бозо™ легко объяснить даже трёхлетнему ребёнку. Выбираем наугад два элемента, меняем местами, проверяем не привело ли это к успеху. Если нет, то повторяем те же действия – и так до до победного конца.
Может показаться, что BozoSort принипиально не отличается от BogoSort, но это только на первый взгляд. Клоун Бозо™ сортирует со средней временной сложностью O(n x n!) и это же является и верхней границей по времени.
import java.util.Random;
class BozoSortAlgorithm extends SortAlgorithm {
void sort(int a[]) throws Exception {
boolean sorted = false; //Считаем что не отсортировано
while (!sorted) {
//Берём наугад два элемента массива...
int index1 = Randomize(a.length);
int index2 = Randomize(a.length);
//... и меняем их местами
int temp = a[index2];
a[index2] = a[index1];
a[index1] = temp;
pause(index1, index2);
//Отсортировали?
sorted = true;
for (int i = 1; i < a.length; i++) {
if (a[i-1] > a[i]) {
pause(i, i-1);
sorted = false;
break;
}
}
}
}
//Выбираем в массиве случайный индекс
private int Randomize( int range ) {
double rawResult;
rawResult = Math.random();
return (int) (rawResult * range);
}
}
Сортировка перестановками (PermSort)
Взглянем на задачу сортировки сквозь призму комбинаторики. Любой массив – обычное конечное множество из n элементов, для которого существует n! перестановок. Некоторые из них – массив в упорядоченном состоянии. Составив алгоритм для перебора всех перестановок, мы неизбежно найдём ту самую.
Худшая сложность по времени как и у клоуна Бозо™ – O(n х n!). А вот с лучшей дела обстоят получше – О(n).
class PermSortAlgorithm extends SortAlgorithm {
//Отсортировали подмассив?
boolean issorted(int a[], int i) throws Exception {
for (int j = a.length-1; j > 0; j--) {
//Сравниваем и если что - меняем
compex(j, j - 1);
if(a[j] < a[j - 1]) {
return false;
}
}
return true;
}
//Рекурсивный PermSort
boolean sort(int a[], int i) throws Exception {
int j;
// Проверка на упорядоченность подмассива
if (issorted(a, i)) {
return true;
}
// Подмассив не отсортирован.
// Поэтому перебираем перестановки элементов.
for(j = i+1; j < a.length; j++) {
compex(i, j);
//Попробуем-ка переставить
int T = a[i];
a[i] = a[j];
a[j] = T;
//Рекурсивно призываем новую перестановку
if(sort(a, i + 1)) {
return true;
}
//Возврат к исходному состоянию
T = a[i];
a[i] = a[j];
a[j] = T;
}
return false;
}
//Сортируем исходный массив с помощью алгоритма PermSort.
void sort(int a[]) throws Exception {
sort(a, 0);
}
}
Придурковатая сортировка (Stooge sort)
Сортировка названа в честь комик-труппы «Three Stooges» («Три недоумка») веселившей американскую публику в прошлом веке: с начала 30-х по конец 60-х. К слову, всего «недоумков» было шестеро, за 4 десятилетия творческой деятельности состав трио иногда менялся.
Развесёлая троица специализировалась на фарсе и эксцентрике. Также ведёт себя и сортировка: подобно карикатурному персонажу она безумно мечется по массиву; как и положено в буффонаде – после нелепых приключений с главным героем всё хорошо. Массив отсортирован, happy end.
class StoogeSortAlgorithm extends SortAlgorithm {
void sort(int a[], int lo, int hi) throws Exception {
//Сравниваем/меняем элементы на концах отрезка
if(a[lo] > a[hi]) {
int T = a[lo];
a[lo] = a[hi];
a[hi] = T;
}
//Меньше трёх?
if(lo + 1 >= hi) return;
//Чему равна одна треть?
int third = (hi - lo + 1) / 3;
sort(a, lo, hi - third); //Для первых 2/3 массива
sort(a, lo + third, hi); //Для последних 2/3 массива
sort(a, lo, hi - third); //Для первых 2/3 массива
}
//Вызываем сортировку для всего массива
void sort(int a[]) throws Exception {
sort(a, 0, a.length-1);
}
}
Берём отрезок массива (вначале это весь массив) и сравниваем элементы на концах отрезка. Если слева больше чем справа, то, естественно, меняем местами.
Затем, если в отрезке не менее трёх элементов, то тогда:
1) вызываем Stooge sort для первых 2/3 отрезка;
2) вызываем Stooge sort для последних 2/3 отрезка;
3) снова вызываем Stooge sort для первых 2/3 отрезка.
Сложность алгоритма подсчитана подкупающе точно: O(nlog 3 / log 1.5). Это не какие-то там мутные O(n).
Сортировка Бабушкина (Babushkin sort)
Сам Бабушкин непосредственно не является автором метода, однако именно глубокие идеи Алексея легли в основу алгоритма.
Участник региональной образовательной программы для одарённых школьников и молодёжи «Будущее Алтая». Победитель конкурса «Старт в науку».
Грантополучатель программы «У.М.Н.И.К.» проводимой Фондом содействию развития малых форм предприятий в научно-технической сфере.
Разработчик запатентованного антивируса «Иммунитет». Создатель оригинального гаджета «Флешка-маркер». Автор принципиально нового алгоритма архивации файлов.
По приглашению компании Microsoft принимал непосредственное участие в тестировании бета-версии Windows 8.
Алексей Бабушкин
Пусть дан массив из n элементов. Последовательность перемещений элементов на свои места представима в виде ряда n-ричных одноразрядных чисел. Эту последовательность также можно считать многоразрядным n-ричным числом (назовём его числом Бабушкина). Каждый разряд этого числа – индекс позиции массива, в которую нужно вставить очередной элемент. Как получить такое число? Если число Бабушкина представить в 10-чном виде, получим большое (или не очень, зависит от размера массива) число, дописываем перед этим число 0, — получаем дробное число в диапазоне от 0 до 1, с некоторым числом знаков после запятой, а дальше всё просто — подбираем 2 таких целочисленных числа, частное которых даст нам искомое число в диапазоне от 0 до 1 с точностью совпадений до последнего знака. Найдём 2 таких числа – автоматически получаем последовательность перестановок, упорядочивающую массив.
Кому-то что-то не ясно? Сортировка Бабушкина пошагово:
1) Допустим, нужно отсортировать массив из n элементов (индексация начинается с нуля, индекс последнего элемента 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 + 4) Берём в массиве n — 1 элемент и помещаем его в дополнительный массив на позицию, индекс которой равен последней цифре в n-ричном представлении числа полученном на шаге 4.
n + 5) Переносим все элементы из дополнительного массива в основной.
n + 6) PROFIT!!!
Преимущество сортировки Бабушкина перед любым другим методом очевидно – упорядочивание осуществляется с минимальными затратами, элементы сразу вставляются на свои места. Всё строится на использовании ряда n-ричных чисел, которые суть изначально правильная последовательность перемещений, приводящая к необходимому результату. Это делает сортировку Бабушкина бесспорным лидером по временной сложности – худший, средний и лучший результат – O(n). Нужно только подобрать два числа, которые при делении одного на другое сразу дадут самую экономную последовательность.
На этом всё, экспресс-экскурс в мир альтернативных сортировок окончен, благодарю за внимание. Если не сложно, заполните карточку для голосования, прилагаемую к раздаточным материалам лекции.
Отдельная благодарность Патрику Морину (Patrick Morin) за любезно предоставленные java-примеры.
Автор: valemak
