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

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:15:18Z

rollbackEdits.php mass rollback

185.220.102.8 в 05:54, 1 сентября 2022

2022-09-01T05:54:01Z

Lyobzik: Исправлено вычисление диапазона значений в блоке

2016-12-03T06:29:06Z

Исправлено вычисление диапазона значений в блоке

Lyobzik: Исправленно вычисление граничных значений блока

2016-12-03T06:21:31Z

Исправленно вычисление граничных значений блока

Конспектор в 12:04, 4 июня 2015

2015-06-04T12:04:48Z

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

2015-06-04T07:48:30Z

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

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

2015-06-04T06:39:10Z

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

Конспектор в 20:29, 3 июня 2015

2015-06-03T20:29:34Z

Конспектор в 20:05, 3 июня 2015

2015-06-03T20:05:21Z

Конспектор: Отмена правки 47312 участника Конспектор (обсуждение)

2015-06-03T12:04:39Z

Отмена правки 47312 участника Конспектор (обсуждение)

← Предыдущая		Версия 16:15, 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 Майкл Наки].
−	\|}
−
	[[Файл:Bucket-sort-example1.jpg\|right\|400px\|thumb\|Пример работы рекурсивного Bucketsort.]]		[[Файл:Bucket-sort-example1.jpg\|right\|400px\|thumb\|Пример работы рекурсивного Bucketsort.]]
	'''Карманная сортировка''' (англ. ''Bucket sort'') {{---}} алгоритм [[Сортировки\|сортировки]], основанный на предположении о равномерном распределении входных данных.		'''Карманная сортировка''' (англ. ''Bucket sort'') {{---}} алгоритм [[Сортировки\|сортировки]], основанный на предположении о равномерном распределении входных данных.

← Предыдущая		Версия 05:54, 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 Майкл Наки].
		+	\|}
		+
	[[Файл:Bucket-sort-example1.jpg\|right\|400px\|thumb\|Пример работы рекурсивного Bucketsort.]]		[[Файл:Bucket-sort-example1.jpg\|right\|400px\|thumb\|Пример работы рекурсивного Bucketsort.]]
	'''Карманная сортировка''' (англ. ''Bucket sort'') {{---}} алгоритм [[Сортировки\|сортировки]], основанный на предположении о равномерном распределении входных данных.		'''Карманная сортировка''' (англ. ''Bucket sort'') {{---}} алгоритм [[Сортировки\|сортировки]], основанный на предположении о равномерном распределении входных данных.

@@ Строка 38: / Строка 38: @@
          minElement = '''minimum'''(minElement, array[i])
          maxElement = '''maximum'''(maxElement, array[i])
      '''for''' i = 0  '''to''' array.length - 1
          index = int(array[i] * numBuckets / range)
@@ Строка 46: / Строка 47: @@
          '''for''' k = 0 '''to''' buckets[i].length - 1
              добавим buckets[i][k] в конец answer
      '''return''' answer
 ==Асимптотика==

@@ Строка 18: / Строка 18: @@
      '''if''' array.length < 2 '''or''' minElement == maxElement
          '''return''' array;
      '''for''' i = 0  '''to''' array.length - 1
          index = int(array[i] * numBuckets / range)
          добавим array[i] в конец buckets[index]
-         bucketsMinimum[i] = minimum(buckets[index], array[i])
+         minBucktes[index] = '''minimum'''(buckets[index], array[i])
-         bucketsMaximum[i] = maximum(buckets[index], array[i])
+         maxBuckets[index] = '''maximum'''(buckets[index], array[i])
      '''for''' i = 0 '''to''' numBuckets - 1
          buckets[i] = bucketSort(buckets[i], minBucktes[i], maxBuckets[i])
@@ Строка 28: / Строка 29: @@
          '''for''' k = 0 '''to''' buckets[i].length - 1
              добавим buckets[i][k] в конец answer
      '''return''' answer
 ==== Нерекурсивная реализация ====
   '''double[]''' bucketSort('''double[]''' array)

@@ Строка 1: / Строка 1: @@
 [[Файл:Bucket-sort-example1.jpg|right|400px|thumb|Пример работы рекурсивного Bucketsort.]]
-'''Карманная сортировка''' (англ. ''Bucket sort'')  {{---}} алгоритм сортировки, основанный на предположении о равномерном распределении входных данных.
+'''Карманная сортировка''' (англ. ''Bucket sort'')  {{---}} алгоритм [[Сортировки|сортировки]], основанный на предположении о равномерном распределении входных данных.
 == Алгоритм сортировки ==
 === Принцип работы ===
 Для карманной сортировки нужно разбить элементы массива входных данных на <tex>k</tex> блоков (карманов, корзин). Далее каждый из таких блоков сортируется либо другой сортировкой, либо рекурсивно тем же методом разбиения. После сортировок внутри каждых блоков данные записываются в массив в порядке разбиения на блоки. При этом нужно учитывать, что данная сортировка работает только в том случае, если разбиение на блоки производится таким образом, чтобы элементы каждого следующего блока были больше предыдущего.
 === Реализация ===
@@ Строка 16: / Строка 18: @@
      '''if''' array.length < 2 '''or''' minElement == maxElement
          '''return''' array;
      '''for''' i = 0  '''to''' array.length - 1
          index = int(array[i] * numBuckets / range)
@@ Строка 35: / Строка 36: @@
          minElement = '''minimum'''(minElement, array[i])
          maxElement = '''maximum'''(maxElement, array[i])
      '''for''' i = 0  '''to''' array.length - 1
          index = int(array[i] * numBuckets / range)
          добавим array[i] в конец buckets[index]
      '''for''' i = 0 '''to''' numBuckets - 1
-         buckets[i] = quickSort(buckets[i])
+         buckets[i] = sort(buckets[i])
      '''for''' i = 0 '''to''' numBuckets - 1
          '''for''' k = 0 '''to''' buckets[i].length - 1
@@ Строка 53: / Строка 53: @@
 <tex> T(n) = \Theta(n) + \sum\limits_{i = 1}^k O(n_i</tex> <tex> \log n_i) + \Theta(k)</tex>, где <tex> T(n) </tex> время работы алгоритма карманной сортировки.
-<tex> E[n_i] = \frac {n}{k} </tex>
+<tex> E[n_i] = \dfrac {n}{k} </tex>
 То есть, если <tex> n \sim k \Rightarrow  E[T(n)] = \Theta(n) </tex>
@@ Строка 62: / Строка 62: @@
 ==Источники информации==
-* [http://en.wikipedia.org/wiki/Bucket_sort Wikipedia - Bucket sort]
+* [http://en.wikipedia.org/wiki/Bucket_sort Wikipedia — Bucket sort]
 * [http://www.google.ru/url?sa=t&rct=j&q=&esrc=s&source=web&cd=10&ved=0CI0BEBYwCQ&url=http%3A%2F%2Fcs.iupui.edu%2F~xkzou%2Fteaching%2FCS580%2FSortinginlineartime.ppt&ei=d7fUT8WWIs3S4QSkkPT-Ag&usg=AFQjCNEUbmlVNhSgrJKV9-QjPBwU6U0obQ&sig2=3yaysrpuwVjmyhjBCpyBeQ Презентация о линейных сортировках]

@@ Строка 67: / Строка 67: @@
 * [https://www-927.ibm.com/ibm/cas/hspc/student/algorithms/BucketSort.html Описание алгоритма с реализацией рекурсивной версии на языке Java]
 [[Категория: Дискретная математика и алгоритмы]]
-[[Категория: Сортировка]]
+[[Категория: Сортировки]]
 [[Категория: Другие сортировки]]