Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

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

Anna | 4.06.2014 | нет комментариев

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

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

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

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

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

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

image
Средняя трудность по времени: O(n x n!). Есть также и лучшая: твует n! перегруппировок. Некоторые из них – массив в упорядоченном состоянии. Составив алгорифм для перебора всех перегруппировок, мы неминуемо найдём ту самую.

image
Худшая трудность по времени как и у клоуна Бозо™ – 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);
	}

}

image
Берём отрезок массива (сначала это каждый массив) и сопоставляем элементы на концах отрезка. Если слева огромнее чем справа, то, безусловно, меняем местами.
После этого, если в отрезке не менее трёх элементов, то тогда:
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-го курса АлтГТУ.

Участник территориальной образовательной программы для одарённых школьников и мо

Источник: programmingmaster.ru
Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB