18 октября 2013 в 14:44

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

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-примеры.
Ну, а приз зрительских симпатий получает…
17%
(284)
Болотная сортировка
7%
(110)
Сортировка клоуна Бозо
1%
(22)
Сортировка перестановками
7%
(113)
Придурковатая сортировка
68%
(1119)
Сортировка Бабушкина

Проголосовало 1648 человек. Воздержалось 517 человек.

Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.

Валерий Макаров @valemak
карма
60,2
рейтинг 0,1
Похожие публикации
Самое читаемое Разработка

Комментарии (54)

  • +36
    А что насчёт Sleep Sort?
    • +2
      Я так понимаю сложность O(n)
      • +1
        O(max-value + n)
        • –3
          Если max-value — константа, то то что вы написали равно O(n).
          О() определяет то, как увеличится нужное кол-во операций при увеличении числа сортируемых элементов.

          O(C) = 0 так как изменение числа элементов не влияет на результат (например время обращения к элементу массива по индексу не зависит от размера массива)

          O(C+N)=O(C)+O(N) = O(N)
          • +2
            max-value — максимальное значение элемента. И это не константа. И да, я знаю что такое O-большое.
            • –1
              Если это не константа, как оно зависит от числа сортируемых элементов?
              • +4
                Почему оно должно зависеть от числа сортируемых элементов? О-нотация может включать в себя несколько параметров. n и max-value — не зависящие друг от друга
          • 0
            Все-таки max-value не константа, это максимальное значение во входном массиве. И от него действительно зависит время выполнения алгоритма. Для примера, что рост времени выполнения алгоритма нелинеен от n, можно рассмотреть массивы {1, 9999999999999999} и {1, 2, 3, ..., 1000, 9999999999999999}. Оба массива будут сортированы за одинаковое время (если не учитывать время на инициализацию потоков).
            Так что приведенная выше формула верна, O(m + n).
          • +1
            1) А если n константа, то вообще O(1).
            2) Если max-value константа, то O(max-value + n) = O(n)
            Так что странное возражение.
          • +1
            O(C) = 0 так как изменение числа элементов не влияет на результат (например время обращения к элементу массива по индексу не зависит от размера массива)

            O(C+N)=O(C)+O(N) = O(N)
            Серьёзно? За O(C) = 0 вообще по рукам бить надо.

            O(C) = O(1)
            C + n = O(n)
      • 0
        SleepSort не зависит от N. Время работы алгоритма константное. Зависит от максимального размера сортируемых чисел и времени задержки.
        • +2
          А как же затраты на создание процессов?
          • +5
            Речь идет об алгоритмической сложности. Ей чужды такие низменные вещи, как процессор, память, диск…
            • +1
              А вот и нет, эта операция, сколь бы мало времени она не занимала в асимптотической оценке должна участвовать. При достаточно больших n, и малых значениях чисел, время работы будет вести себя линейно по n.
              • +3
                Не могу смотреть на такую несправедливость, так что поддержу.

                В SleepSort всё равно нужно из главного потока создать N вспомогательных, ну или, если переиспользовать вспомогательные потоки, как ниже предлагают, то N раз передать информацию о наличии числа в нужный поток.

                Следовательно даже если пренебречь временем работы шедьюлера ОС, мы должны сделать минимум N операций в основном потоке.

                Интересен тот факт, что если мы задумаемся как мог бы быть реализован шедьюлер (очередь с приоритетами = куча например), то получим O(ln(N)) на вставку, и общее время работы сортировки в привычные O(N ln(N))
          • –3
            Можно заранее создать тредпул с количеством тредов равным максимальному размеру сортируемых чисел. Время его создания будет константным и не зависит от числа сортируемых элементов.
            • +1
              Сама команда sleep имеет не нулевую задержку. Кроме того операция передачи команды потоку тоже является действием и ее нельзя игнорировать.
          • –2
            В некотором смысле SleepSort это временнОе представление radix sort. Только вместо индекса в массиве у вас секунды.
            • +2
              Только не radix sort, а сортировка подсчетом. И у нее сложность будет именно O(n+k): википедия
        • +3
          Время работы алгоритма константное

          Очевидно, что это не так. Доказательство — наличие цикла while с количеством итераций равным количеству элементов.
          • 0
            Да. Согласен. Количество сортируемых элементов может быть любым. А значит время запуска алгоритма не ограничено и линейно растет с числом элементов.
            Спасибо.
            • –2
              Да, видимо в этом и есть причина спора. Считать ли операцию запуска алгоритма частью алгоритма?
              Если да, то линейное. Если нет — константа.
              • 0
                Дело не только в запуске. Потоки не завершают свое выполнение мгновенно, и Sleep не занимает строго заданное количество времени.
                Например, сортировка массива из 10 одинаковых элементов и 1000 одинаковых элементов с теми же значениями займет разное время. Хотя в этом случае зависимость вряд ли будет линейной.
                • 0
                  Задержку придётся задавать в единицах, пропорциональных N — чтобы массив из двойки и N-1 единиц отсортировался правильно (для этого нужно, чтобы все N значений попали в очередь быстрее, чем за 1 единицу задержки). Так что время при правильной реализации будет O(N*max_value) :(
      • 0
        Так зависит все от планировщика ОС. Он собственно и занимается сортировкой, решая, какой процесс пора пробудить. Может он в очередь с приоритетом их выстраивает, тогда это будет по сути heapsort.
    • 0
      Получалась слишком долгая анимация, пришлось отказаться )))
  • +24
    А как же StackSort?
  • –2
    Бабушкин рулит — все-таки наш человек. :)))
  • +8
    Вот вы смеетесь, а вычислиние числа Бабушкина весьма тривиальная задача.
    Решение
    Для этого я предлагаю использовать дополнительный, третий массив. Отсортируем 1-й массив QuickSort-ом, например. Результат запишем в 3-й массив. Далее, мы можем построить таблицу соответствия, из которой мы и получаем число Бабушкина.

    Пример:
    Массив-1:
    3 1 2 5
    

    Массив-3 (уже заполненный):
    1 2 3 5
    

    Таблица соответствия:

    [0] > [2]
    [1] > [0]
    [2] > [1]
    [3] > [3]
    


    (поскольку один разряд указывает на один элемент массива, при формировании таблицы индексы необходимо перевести в систему счисления с основанием n, где n — длина сортируемого массива)

    Несложно заметить, что числом Бабушкина является 2-й столбец (при чтении сверху вниз). Запишем его:
    2013
    

    (не забываем, что число у нас в четверичной системе счисления)

    Для вычисления чисел, при делении которых, дробная часть равна числу Бабушкина, нам необходимо вычислить логарифм этого числа по основанию n, где n — длинна массива (d). Теперь, если возвести n в степень d+1, получим делитель. Число Бабушкина же будет делимым.

    Все, можно приступать к сортировке Бабушкина.



    • +8
      Есть ещё вариант вычислить число Бабушкина — надо позвонить Бабушкину по телефону и спросить это число.
      По своему опыту скажу, что лучше всего звонить поздно ночью, тогда шанс что Бабушкин будет занят чем-то другим очень низок и это будет сильно способствовать увеличению общей производительности алгоритма.
    • +9
      «Иммунитет» хорошо проявляет себя в паре с другим антивирусом. (Бабушкин)

      Сортировка Бабушкина особенно эффективна в симбиозе с другой сортировкой.
  • +13
    А как же Quantum Bogosort?!

    Алгоритм, в котором предполагается, что теория о множестве вселенных верна. Тогда алгоритм получается следующий:
    1. Проверить отсортирован ли массив?
    2. Если нет, уничтожить вселенную.
    В конце останется лишь вселенная, в которой массив изначально был отсортирован.

    Мой любимый.
    • НЛО прилетело и опубликовало эту надпись здесь
      • +3
        Наихудший вариант, же
        • НЛО прилетело и опубликовало эту надпись здесь
      • +2
        Она не одна. Все Вселенные, в которых массив был отсортирован, продолжат существовать.
        Кстати, вместо Вселенной достаточно уничтожать Наблюдателя. Тогда, с его точки зрения, массив будет отсортирован (по принципу квантового бессмертия).
        • +7
          Сортировка Шредингера. Пока наблюдатель не видит массив, он одновременно отсортирован и не отсортирован.
    • +3
      Просто это работает только на тех платформах, где присутствует инструкция «уничтожить Вселенную».
      • 0
        существуют только Вселенные, допускающие существование платформы, имеющие инструкцию «уничтожить Вселенную» ~©
  • +1
    • 0
      Спасибо за наводку. Как дойдут руки через пару недель сделать продолжение этой темы, то метод сортировки «Разумного замысла» туда обязательно войдёт.
  • +2
    > Клоун Бозо™ сортирует со средней временной сложностью O(n x n!) и это же является и верхней границей по времени.

    Как такое может быть? Ведь в худшем случае мы будем постоянно переставлять одни и те же два элемента, так что верхняя граница — бесконечность. Или вы как-то по другому определяете верхнюю границу для рандомизированных алгоритмов? Верхняя граница только по входным данным, с усреднением по выдаче ГПСЧ?
    • 0
      Вы абсолютно правы. В соответсвующем месте текста добавил примечание по этому поводу.
  • +6
    Кстати зря смеётесь над алгоритмом Бабушкина: как ни странно он даёт вполне пристойную сортировку.
    Алгоритм: строим цепную дробь для числа Бабушкина. В какой-то момент либо цепная дробь закончится (т.к. конечна), либо ошибка будет меньше последнего разряда (и поскольку отклонение приближения цепными дробями на каждом шаге меняет знак, эта либо следующая дробь подойдёт под условие «совпадает с точностью до последнего знака»). Каждый шаг цепной дроби сводится к обращению длинного числа (разделить 1 на него).
    Рост знаменателя приближения цепной дробью, насколько я помню, оценивается как y^k, где k — количество шагов, y — константа. При этом отклонение от искомого числа Бабушкина не больше 1/(квадрат знаменателя).

    Сложение-вычитания длинных чисел — линейны, количество шагов — логарифм. Таким образом, оценка скорости поиска пары чисел для числа Бабушкина: O(сложность деления длинных чисел * logn). Сложность деления 1 на длинное число по этой статье сводится к сложности умножения
    citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.71.7394&rep=rep1&type=pdf
    т.е. O(n * logn).

    Таким образом, алгоритм будет работать за O(n*log^2(n)) — что весьма неплохо.
  • 0
    Когда в детстве только знакомился с программированием, довольно быстро придумал свой алгоритм сортировки. Создаем второй массив такого же размера. Обходим исходный массив в поиске наименьшего элемента. Записываем в новый. Снова обходим первый массив в поиске наименьшего но большего чем предыдущий и т.д. Сложность очевидно O(n x n). Причем стабильно при любом раскладе.
    О каноничных алгоритмах сортировки узнал почему-то только в универе.
    PS: сейчас подумал, что в алгоритме очевидный баг: если в исходном массиве есть одинаковые элементы, то в результирующем они будут в единственном экземпляре.
    • +2
      Может вы не в курсе, но ваш алгоритм — самая что ни на есть каноничная «сортировка выбором», о которой написано даже на википедии
      • +3
        Ну, «изобрести» в детстве то что уже давно придумано — это святое. Если в юном возрасте есть желание и попытки «вносить свой вклад в науку» то можно только поприветствовать. Лишь бы в дальнейшем это не приобретало клинических форм как у некоторых.

        Кроме того, приведённый способ не является «самой что ни на есть каноничной «сортировкой выбором». Об этом свидетельствует и честно признаваемая автором применимость только к массивам с неповторяющимися элементами. А также использование дополнительного массива (в классической selection sort расходов на дополнительную память нет).
  • –11
    нужно добавить ещё один пункт к голосованию: «В сортах говна не разбираюсь» :)
  • +1
    Бабушкин опять на пике популярности. Я все жду, когда он изобретет свои структуры данных типа «деревьев Бабушкина». Так же очень жду открытий в теории графов — «граф Бабушкина», «критерий Бабушкинности графа» и т.д…
  • +2
    Добавлю аналог Bogo: сортировка болотным пузырьком.

    Если упрощённо, то:
    function BogoSort2(array){
    array.sort(function(){ return Math.random() > 0.5; });
    if( !isSorted(array) ) return BogoSort2(array);
    return array;
    }
    function isSorted(array){
    for(var i = 1, l = array.length; i < l; i++){
    if(array[i] < array[i-1]) return false;
    }
    return true;
    }

    // заранее хочу извиниться за то, что 1. саму сортировку пузырьком лень писать, тем более, что во многих языках она есть. 2. не на Java, как в посте, а на JS. 3. отсутствие тега source, карма не позволяет.
    • 0
      Для заинтересовавшихся оформлю в более наглядном виде:

      function BogoSort2(array) {
      
          array.sort(function() {
      
              return Math.random() > 0.5; 
      
          });
      
          if (!isSorted(array)) return BogoSort2(array);
      
          return array;
      
      }
      
      function isSorted(array) {
      
          for(var i = 1, l = array.length; i < l; i++) {
      
              if(array[i] < array[i-1]) return false;
      
          }
      
          return true; 
      
      }
      
  • +1
    По этому поводу был даже выпуск xkcd http://xkcd.com/1185/
  • +1
    А знаю еще более худший и варварский способ!
    Называется — генетический алгоритм :-)
    Берем начальный массив, массив генома — порядок расположения элементов в сортированном массиве.
    А дальше тупо перебираем ВСЕ геномы и постоянно сохраняем лучший.
    Можно оптимизировать, но тогда упадет временная сложность :-)
    Итак, все то же, но по шагам:
    1)задаем массив последовательными значениям от 1 до n. Говорим, что он лучший
    2)проходимся по orig[genom[i]] и проверяем на неубываемость
    3)сверяем количество неубывающих элементов текущего массива с количеством неубывающих элементов лучшего массива. Если текущий массив лучше лучшего, то он становится лучшим :-)
    4)Если можем, формируем новую последовательность(перебором) и идем на шаг 2. Если не можем, выходим.
    5) формируем итоговый массив.

    Итоговая сложность — n*(2n+2)
  • 0
    Также отмечу, что тем не менее BozoSort в среднем всё равно будет сортировать быстрее чем BogoSort. Просто потому, что после каждого обмена массив проверяется на упорядоченность. В BogoSort часты случаи, когда массив находится в упорядоченном состоянии, однако если в этот момент не произвести проверку, а перемешивать далее, то вожделенное состояние осортированности на время утрачивается.

    Что за бред? Сам процесс проверки массива на упорядоченность слишком медленный. Поэтому BozoSort работает медленнее, просто за счет более частых проверок.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.