Сортировка пузырьком - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:41:49Z

rollbackEdits.php mass rollback

185.244.195.157 в 03:32, 1 сентября 2022

2022-09-01T03:32:18Z

Darkblack1997: /* Источники информации */

2017-01-22T21:31:56Z

‎Источники информации

Darkblack1997: /* Источники информации */ категория

2017-01-22T21:31:19Z

‎Источники информации: категория

Darkblack1997: /* Сортировка расческой */ n/k - дробь

2017-01-22T21:26:45Z

‎Сортировка расческой: n/k - дробь

Darkblack1997: /* Сложность */ увеличение дробей

2017-01-22T21:24:39Z

‎Сложность: увеличение дробей

Darkblack1997: /* Сортировка перемешиванием */ изменила второе условие

2017-01-22T21:19:30Z

‎Сортировка перемешиванием: изменила второе условие

Darkblack1997: /* Сортировка чет-нечет */ знак равенства

2017-01-22T21:17:14Z

‎Сортировка чет-нечет: знак равенства

Darkblack1997: /* Сортировка перемешиванием */ "false" переписано курсивом

2017-01-22T21:14:19Z

‎Сортировка перемешиванием: "false" переписано курсивом

Darkblack1997: объединены разделы "Алгоритм" и "Псевдокод"; отступы, пробелы после тире, равно и т.п., исправление орфографических ошибок

2017-01-22T21:09:04Z

объединены разделы "Алгоритм" и "Псевдокод"; отступы, пробелы после тире, равно и т.п., исправление орфографических ошибок

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

← Предыдущая		Версия 16:41, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~	+	'''Сортировка простыми обменами''', '''сортировка пузырьком''' (англ. ''bubble sort'') — один из квадратичных алгоритмов сортировки.
−	\|+
−	~~\|-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 Майкл Наки].
−	\|}
−
−	'''Сортировка простыми обменами''', '''сортировка пузырьком''' (англ. ''bubble sort'') — один из квадратичных алгоритмов сортировки.

	== Алгоритм ==		== Алгоритм ==

← Предыдущая		Версия 03:32, 1 сентября 2022
Строка 1:		Строка 1:
−	'''Сортировка простыми обменами''', '''сортировка пузырьком''' (англ. ''bubble sort'') — один из квадратичных алгоритмов сортировки.	+	{\| 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 Майкл Наки].
		+	\|}
		+
		+	'''Сортировка простыми обменами''', '''сортировка пузырьком''' (англ. ''bubble sort'') — один из квадратичных алгоритмов сортировки.

	== Алгоритм ==		== Алгоритм ==

@@ Строка 174: / Строка 174: @@
 [[Категория: Дискретная математика и алгоритмы]]
 [[Категория: Сортировка]]
-[[Категория: Квадратичная сортировка]]
+[[Категория: Квадратичные сортировки]]

← Предыдущая		Версия 21:31, 22 января 2017
Строка 174:		Строка 174:
	[[Категория: Дискретная математика и алгоритмы]]		[[Категория: Дискретная математика и алгоритмы]]
	[[Категория: Сортировка]]		[[Категория: Сортировка]]
		+	[[Категория: Квадратичная сортировка]]

@@ Строка 133: / Строка 133: @@
           swap(a[i], a[i + jump])
           swapped = ''true''
-Пояснения: Изначально расстояние между сравниваемыми элементами равно <tex> n/k </tex>, где <tex> k = 1{.}3 </tex> {{---}} оптимальное число для этого алгоритма. Сортируем массив по этому расстоянию, потом уменьшаем его по этому же правилу. Когда  расстояние между сравниваемыми элементами достигает единицы, массив досортировывается обычным пузырьком.
+Пояснения: Изначально расстояние между сравниваемыми элементами равно <tex dpi=150> \frac{n}{k} </tex>, где <tex> k = 1{.}3 </tex> {{---}} оптимальное число для этого алгоритма. Сортируем массив по этому расстоянию, потом уменьшаем его по этому же правилу. Когда  расстояние между сравниваемыми элементами достигает единицы, массив досортировывается обычным пузырьком.
 === Сортировка перемешиванием  ===

@@ Строка 37: / Строка 37: @@
 В данной сортировке выполняются всего два различных вида операции: сравнение элементов и их обмен. Поэтому время всего алгоритма <tex> T = T_1 + T_2 </tex>, где <tex> T_1 </tex> {{---}} время, затрачиваемое на сравнение элементов, а <tex> T_2 </tex> {{---}} время, за которое мы производим все необходимые обмены элементов.
-Так как в алгоритме меняться местами могут только соседние элементы, то каждый обмен уменьшает количество [[Таблица инверсий|инверсий]] на единицу. Следовательно, количество обменов равно количеству инверсий в исходном массиве вне зависимости от реализации сортировки. Максимальное количество инверсий содержится в массиве, элементы которого отсортированы по убыванию. Несложно посчитать, что количество инверсий в таком массиве <tex> \frac {n (n - 1)} {2} </tex>. Получаем, что <tex> T_2 = O(n^2) </tex>.
+Так как в алгоритме меняться местами могут только соседние элементы, то каждый обмен уменьшает количество [[Таблица инверсий|инверсий]] на единицу. Следовательно, количество обменов равно количеству инверсий в исходном массиве вне зависимости от реализации сортировки. Максимальное количество инверсий содержится в массиве, элементы которого отсортированы по убыванию. Несложно посчитать, что количество инверсий в таком массиве <tex dpi=150> \frac {n (n - 1)} {2} </tex>. Получаем, что <tex> T_2 = O(n^2) </tex>.
 В неоптимизированной реализации на каждой итерации внутреннего цикла производятся <tex> n - 1 </tex> сравнений, а так как внутренний цикл запускается также <tex> n - 1 </tex> раз, то за весь алгоритм сортировки производятся <tex> (n - 1)^2 </tex> сравнений.
-В оптимизированной версии точное количество сравнений зависит от исходного массива. Известно, что худший случай равен <tex> \frac {n (n - 1)} {2} </tex>, а лучший {{---}} <tex> n-1 </tex>. Следовательно, <tex> T_1 = O(n^2) </tex>.
+В оптимизированной версии точное количество сравнений зависит от исходного массива. Известно, что худший случай равен <tex dpi=150> \frac {n (n - 1)} {2} </tex>, а лучший {{---}} <tex> n-1 </tex>. Следовательно, <tex> T_1 = O(n^2) </tex>.
 В итоге получаем <tex> T = T_1 + T_2 = O(n^2) + O(n^2) = O(n^2) </tex>.

@@ Строка 148: / Строка 148: @@
           swap(a[i], a[i + 1])
           swapped = ''true''
-      '''if''' swapped = ''false''
+      '''if''' !swapped
         '''break'''
       swapped = ''false''

@@ Строка 107: / Строка 107: @@
   '''function''' oddEvenSort(a):
     '''for''' i = 0 '''to''' n - 1
-      '''if''' i '''mod''' 2 = 0
+      '''if''' i '''mod''' 2 == 0
         '''for''' j = 2 '''to''' n - 1 '''step''' 2
           '''if''' a[j] < a[j - 1]