Блинная сортировка - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:35:43Z

rollbackEdits.php mass rollback

185.220.100.254 в 04:14, 1 сентября 2022

2022-09-01T04:14:25Z

85.26.222.98 в 14:03, 23 января 2016

2016-01-23T14:03:39Z

213.21.46.212 в 18:32, 20 января 2016

2016-01-20T18:32:47Z

213.21.46.212 в 18:25, 20 января 2016

2016-01-20T18:25:56Z

213.21.46.212 в 18:18, 20 января 2016

2016-01-20T18:18:55Z

213.21.46.212 в 18:04, 20 января 2016

2016-01-20T18:04:15Z

Внесённые изменения

213.21.46.212 в 17:03, 20 января 2016

2016-01-20T17:03:47Z

Внесённые изменения

Yurik: Удалено содержимое страницы

2012-06-08T15:18:54Z

Удалено содержимое страницы

Yurik: Новая страница: «{{В разработке}} Категория: Дискретная математика и алгоритмы Категория: Сортировки»

2012-06-08T14:52:55Z

Новая страница: «{{В разработке}} Категория: Дискретная математика и алгоритмы Категория: Сортировки»

Новая страница

{{В разработке}}

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировки]]

← Предыдущая		Версия 16:35, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
−

	'''Блинная сортировка''' (англ. ''pancake sorting'') {{---}} алгоритм [[Сортировки \| сортировки]] с помощью одной операции {{---}} переворота элементов последовательности до какого-то индекса (префикса последовательности). Разумеется, разрешены сравнения, при оценке времени работы этого алгоритма оценивается количество переворотов, а не сравнений. Название алгоритма пошло от изначальной задачи отсортировать стопку блинов по возрастанию размера.		'''Блинная сортировка''' (англ. ''pancake sorting'') {{---}} алгоритм [[Сортировки \| сортировки]] с помощью одной операции {{---}} переворота элементов последовательности до какого-то индекса (префикса последовательности). Разумеется, разрешены сравнения, при оценке времени работы этого алгоритма оценивается количество переворотов, а не сравнений. Название алгоритма пошло от изначальной задачи отсортировать стопку блинов по возрастанию размера.

← Предыдущая		Версия 04:14, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
		+

	'''Блинная сортировка''' (англ. ''pancake sorting'') {{---}} алгоритм [[Сортировки \| сортировки]] с помощью одной операции {{---}} переворота элементов последовательности до какого-то индекса (префикса последовательности). Разумеется, разрешены сравнения, при оценке времени работы этого алгоритма оценивается количество переворотов, а не сравнений. Название алгоритма пошло от изначальной задачи отсортировать стопку блинов по возрастанию размера.		'''Блинная сортировка''' (англ. ''pancake sorting'') {{---}} алгоритм [[Сортировки \| сортировки]] с помощью одной операции {{---}} переворота элементов последовательности до какого-то индекса (префикса последовательности). Разумеется, разрешены сравнения, при оценке времени работы этого алгоритма оценивается количество переворотов, а не сравнений. Название алгоритма пошло от изначальной задачи отсортировать стопку блинов по возрастанию размера.

@@ Строка 1: / Строка 1: @@
-'''Блинная сортировка''' (англ. ''pancake sorting'') {{---}} алгоритм [[Сортировки | сортировки]] с помощью одной операции {{---}} переворота элементов последовательности до какого-то индекса. Разумеется, разрешены сравнения, при оценке времени работы этого алгоритма оценивается количество переворотов, а не сравнений. Название алгоритма пошло от изначальной задачи отсортировать стопку блинов по возрастанию размера.
+'''Блинная сортировка''' (англ. ''pancake sorting'') {{---}} алгоритм [[Сортировки | сортировки]] с помощью одной операции {{---}} переворота элементов последовательности до какого-то индекса (префикса последовательности). Разумеется, разрешены сравнения, при оценке времени работы этого алгоритма оценивается количество переворотов, а не сравнений. Название алгоритма пошло от изначальной задачи отсортировать стопку блинов по возрастанию размера.
 == Корректность ==
 Для начала покажем, что любую последовательность можно отсортировать с помощью блинной сортировки. Для этого будет предложен алгоритм, позволяющий отсортировать любой массив, сделав не более <tex>2n</tex> операций, где <tex>n</tex> {{---}} размер массива.
-Найдём максимальный элемент последовательности с номером <tex>i</tex> и развернём префикс массива до <tex>i</tex>-ого элемента. Теперь максимальный элемент находится в начале массива. Развернём весь массив, теперь максимальный элемент находится в конце массива. Сделаем то же самое рекуррентно для префикса длины <tex>n-1</tex>. Переместим второй по возрастанию элемент в конец подотрезка, после чего последние два элемента будут отсортированы, и продолжим для префикса длины <tex>n-2</tex>. Таким образом, на каждой итерации мы сделаем две операции, и всего итераций будет не больше <tex>n</tex> (их может быть меньше <tex>n</tex>: если после <tex>i</tex>-ой итерации отсортированным окажется суффикс длины больше, чем <tex>i+1</tex>, можно рекурсивно запустить алгоритм на префиксе длины <tex>n-i-k</tex> вместо <tex>n-i-1</tex>). Тогда суммарное количество операций не превосходит <tex>2n</tex> и любая последовательность может быть отсортирована таким образом.
+Найдём максимальный элемент последовательности с номером <tex>i</tex> и развернём префикс массива до <tex>i</tex>-го элемента. Теперь максимальный элемент находится в начале массива. Развернём весь массив, теперь максимальный элемент находится в конце массива. Сделаем то же самое рекуррентно для префикса длины <tex>n-1</tex>. Переместим второй по возрастанию элемент в конец подотрезка, после чего последние два элемента будут отсортированы, и продолжим для префикса длины <tex>n-2</tex>. Таким образом, на каждой итерации мы сделаем две операции, и всего итераций будет не больше <tex>n</tex> (их может быть меньше <tex>n</tex>: если после <tex>i</tex>-ой итерации отсортированным окажется суффикс длины больше, чем <tex>i+1</tex>, можно рекурсивно запустить алгоритм на префиксе длины <tex>n-i-k</tex> вместо <tex>n-i-1</tex>). Тогда суммарное количество операций не превосходит <tex>2n</tex> и любая последовательность может быть отсортирована таким образом.
 == Оценки на количество операций ==
@@ Строка 34: / Строка 34: @@
 ==== Верхняя ====
-Будет предложен алгоритм, который изменит перестановку <tex>\pi</tex> так, чтобы в ней было <tex>n-1</tex> соседство. После этого отсортировать массив можно не более чем за 4 действия (в иллюстрациях дальше показана последовательность действий, состояние в следующей строке получается из состояния в предыдущей одним разворотом префикса):
+Будет предложен алгоритм, который изменит перестановку <tex>\pi</tex> так, чтобы в ней было <tex>n-1</tex> соседств. После этого отсортировать массив можно не более чем за 4 действия (в иллюстрациях дальше показана последовательность действий, состояние в следующей строке получается из состояния в предыдущей одним разворотом префикса):
 {| border="1" style="border-collapse: collapse; float: left; margin-right: 30px;"
@@ Строка 312: / Строка 312: @@
 {{Теорема
-|statement=Предложенный алгоритм создает перестановку с <tex>n-1</tex> соседством не более чем за <tex>\dfrac{5n-7}{3}</tex> итераций.
+|statement=Предложенный алгоритм создает перестановку с <tex>n-1</tex> соседствами не более чем за <tex>\dfrac{5n-7}{3}</tex> итераций.
 |proof=
-Алгоритм всегда завершит работу. На каждой итерации при условии, что в перестановке меньше <tex>n-1</tex> соседств, выполнится одно из условий <tex>1-7</tex>. На каждой итерации создается не меньше одного соседства и ни одного соседства не разрушается, поэтому алгоритм создаст нужную перестановку не больше чем за <tex>n-1</tex> итерацию.
+Алгоритм всегда завершит работу. На каждой итерации при условии, что в перестановке меньше <tex>n-1</tex> соседств, выполнится одно из условий <tex>1-7</tex>. На каждой итерации создается не меньше одного соседства и ни одного соседства не разрушается, поэтому алгоритм создаст нужную перестановку не больше чем за <tex>n-1</tex> итераций.
 Будем называть случай 1 ''действием 1'', случай 2 ''действием 2'', случаи 3 и 6 ''действием 3'', случаи 4, 5 и 7 ''действиями'' 4, 5 и 7 соответственно. Пусть <tex>x_i</tex> обозначает количество действий типа <tex>i</tex>, выполненных за время работы алгоритма. Суммарное число разворотов составит

@@ Строка 426: / Строка 426: @@
 *[http://www.eecs.berkeley.edu/~christos/papers/GP79.pdf William H. Gates; Christos H. Papadimitriou Bounds for sorting by prefix reversal]
-[[Категория: Алгоритмы и структуры данных]]
+[[Категория: Дискретная математика и алгоритмы]]
 [[Категория: Сортировки]]
 [[Категория: Другие сортировки]]

@@ Строка 407: / Строка 407: @@
 {{Теорема
-|statement=Число разворотов, необходимое для сортировки последовательности <tex>\chi</tex>, не меньше <tex>\dfrac{17n}{16}</tex>
+|statement=Число разворотов, необходимое для сортировки последовательности <tex>\chi</tex>, не меньше <tex>\dfrac{17n}{16}</tex>.
 }}
@@ Строка 426: / Строка 426: @@
 *[http://www.eecs.berkeley.edu/~christos/papers/GP79.pdf William H. Gates; Christos H. Papadimitriou Bounds for sorting by prefix reversal]
 [[Категория: Сортировки]]
 [[Категория: Другие сортировки]]

@@ Строка 23: / Строка 23: @@
 Для начала введём некоторые обозначения.
-Пусть <tex>S_n</tex> {{---}} множество перестановок элементов массива длины <tex>n</tex>. Будем считать перестановки строками в <tex>\Sigma^*_n</tex>, где <tex>\Sigma_n=\{1, 2, \ldots, n\}</tex>. Введём бинарное отношение <tex>R: \Sigma^*_n \rightarrow \Sigma^*_n</tex>: <tex>\pi R\sigma</tex> тогда и только тогда, когда <tex>\pi =xy</tex> и <tex>\sigma =x^Ry</tex>, где <tex>\pi, \sigma \in \Sigma^*_n</tex> и <tex>x^R</tex> обозначает развёрнутую <tex>x</tex>.
+Пусть <tex>S_n</tex> {{---}} множество перестановок элементов массива длины <tex>n</tex>. Будем считать перестановки строками в <tex>\Sigma^*_n</tex>, где <tex>\Sigma_n=\{1, 2, \ldots, n\}</tex>. Введём [[Бинарное отношение | бинарное отношение]] <tex>R: \Sigma^*_n \rightarrow \Sigma^*_n</tex>: <tex>\pi R\sigma</tex> тогда и только тогда, когда <tex>\pi =xy</tex> и <tex>\sigma =x^Ry</tex>, где <tex>\pi, \sigma \in \Sigma^*_n</tex> и <tex>x^R</tex> обозначает развёрнутую <tex>x</tex>.
 Пусть <tex>\pi</tex> {{---}} перестановка, тогда <tex>f(\pi)</tex> {{---}} наименьшее <tex>k</tex> такое, что существует последовательность перестановок <tex>\pi_0 R \pi_1 R \ldots R \pi_k = e_n</tex>, где <tex>e_n = 123\ldots n</tex>. Тогда для числа <tex>n</tex> будем обозначать <tex>f(n)</tex> за максимальное <tex>f(\pi)</tex> среди всех <tex>\pi \in S_n</tex>.
@@ Строка 407: / Строка 407: @@
 {{Теорема
-|statement=<tex>f(\chi ) \geqslant \dfrac{17n}{16}</tex>
+|statement=Число разворотов, необходимое для сортировки последовательности <tex>\chi</tex>, не меньше <tex>\dfrac{17n}{16}</tex>
 }}
@@ Строка 427: / Строка 427: @@
 [[Категория: Сортировки]]

← Предыдущая		Версия 15:18, 8 июня 2012
Строка 1:		Строка 1:
−	~~{{В разработке}}~~

−
−	~~[[Категория: Дискретная математика и алгоритмы]]~~
−	~~[[Категория: Сортировки]]~~