Pull to refresh

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

Reading time7 min
Views103K
image

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

Представляю Вашему вниманию ТОП-5 самых нетрадиционных сортировок всех времён и народов.

Младопрограммистам такое полезно показывать в дидактических целях. Всех остальных как минимум позабавит.


Болотная сортировка (BogoSort)


image
С этой сортировкой нужно быть предельно осторожным. Неосмотрительно угодив в трясину, рискуете сгинуть навсегда.

Принцип прост как плесень. Перетряхиваем массив до тех пор пока он внезапно не отсортируется. Процесс может счастливо завершиться сразу, а может длиться до тепловой смерти Вселенной. Это уж как повезёт.



Средняя сложность по времени: 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)


image
Где BogoSort, там и BozoSort. Метод сортировки детского клоуна Бозо легко объяснить даже трёхлетнему ребёнку. Выбираем наугад два элемента, меняем местами, проверяем не привело ли это к успеху. Если нет, то повторяем те же действия – и так до до победного конца.



Может показаться, что BozoSort — это то же что и BogoSort, но это только на первый взгляд. Клоун Бозо сортирует со средней временной сложностью O(n x n!) и это же является и верхней границей по времени.

UPD. Как мне справедливо указали burdakovd и SkidanovAlex в комментариях и личных сообщениях, у сортировки клоуна Бозо, как и у BogoSort нет верхнего предела для худшей временной сложности. Действительно, откуда ей взяться, если в худшем случае в неотсортированном массиве рандом будет вечно менять местами одни и те же два элемента!?

Также отмечу, что тем не менее BozoSort в среднем всё равно будет сортировать быстрее чем BogoSort. Просто потому, что после каждого обмена массив проверяется на упорядоченность. В BogoSort часты случаи, когда массив находится в упорядоченном состоянии, однако если в этот момент не произвести проверку, а перемешивать далее, то вожделенное состояние осортированности на время утрачивается.


Клоун Бозо ещё и искромётно программирует.
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)


image
Взглянем на задачу сортировки сквозь призму комбинаторики. Любой массив – обычное конечное множество из 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)


image
Сортировка названа в честь комик-труппы «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)


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

Краткая справка о Бабушкине
Алексей Бабушкин, программист из Барнаула, предприниматель, инноватор. Студент 4-го курса АлтГТУ.

Участник региональной образовательной программы для одарённых школьников и молодёжи «Будущее Алтая». Победитель конкурса «Старт в науку».

Грантополучатель программы «У.М.Н.И.К.» проводимой Фондом содействию развития малых форм предприятий в научно-технической сфере.

Разработчик запатентованного антивируса «Иммунитет». Создатель оригинального гаджета «Флешка-маркер». Автор принципиально нового алгоритма архивации файлов.

По приглашению компании Microsoft принимал непосредственное участие в тестировании бета-версии Windows 8.

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

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

Пусть дан массив из n элементов. Последовательность перемещений элементов на свои места представима в виде ряда n-ричных одноразрядных чисел. Эту последовательность также можно считать многоразрядным n-ричным числом (назовём его числом Бабушкина). Каждый разряд этого числа – индекс позиции массива, в которую нужно вставить очередной элемент. Как получить такое число? Если число Бабушкина представить в 10-чном виде, получим большое (или не очень, зависит от размера массива) число, дописываем перед этим число 0, — получаем дробное число в диапазоне от 0 до 1, с некоторым числом знаков после запятой, а дальше всё просто — подбираем 2 таких целочисленных числа, частное которых даст нам искомое число в диапазоне от 0 до 1 с точностью совпадений до последнего знака. Найдём 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) Переносим все элементы из дополнительного массива в основной.
n + 6) PROFIT!!!

Преимущество сортировки Бабушкина перед любым другим методом очевидно – упорядочивание осуществляется с минимальными затратами, элементы сразу вставляются на свои места. Всё строится на использовании ряда n-ричных чисел, которые суть изначально правильная последовательность перемещений, приводящая к необходимому результату. Это делает сортировку Бабушкина бесспорным лидером по временной сложности – худший, средний и лучший результат – O(n). Нужно только подобрать два числа, которые при делении одного на другое сразу дадут искомую последовательность.

Есть опытные образцы и работающая программа и всё это работает.


Сортировка Бабушкина на Java.
К сожалению, java-реализацию сортировки Бабушкина найти не удалось. Извините.

На этом всё, экспресс-экскурс в мир альтернативных сортировок окончен, благодарю за внимание. Если не сложно, заполните карточку для голосования, прилагаемую к раздаточным материалам лекции.

Отдельная благодарность Патрику Морину (Patrick Morin) за любезно предоставленные java-примеры.
Only registered users can participate in poll. Log in, please.
Ну, а приз зрительских симпатий получает…
17.23% Болотная сортировка284
6.67% Сортировка клоуна Бозо110
1.33% Сортировка перестановками22
6.86% Придурковатая сортировка113
67.9% Сортировка Бабушкина1119
1648 users voted. 517 users abstained.
Tags:
Hubs:
If this publication inspired you and you want to support the author, do not hesitate to click on the button
Total votes 95: ↑82 and ↓13+69
Comments54

Articles