А что это мы всё об умных да об эффективных алгоритмах? А давайте эту тоскливую осеннюю пятницу развеем чем-нибудь контрпродуктивным!?

Представляю Вашему вниманию ТОП-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(n^{log 3 / log 1.5}). Это не какие-то там мутные O(n).

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

Сам Бабушкин непосредственно не является автором метода, однако именно глубокие идеи Алексея легли в основу алгоритма.

Пусть дан массив из 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-примеры.