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

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:05:27Z

rollbackEdits.php mass rollback

141.98.9.47 в 06:30, 1 сентября 2022

2022-09-01T06:30:57Z

188.130.155.152: cnt[j] должен уменьшаться при формировании вспомогательного массива

2018-04-07T00:05:30Z

cnt[j] должен уменьшаться при формировании вспомогательного массива

Shersh в 17:04, 13 февраля 2015

2015-02-13T17:04:51Z

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

2015-02-13T17:03:57Z

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

Savelin: /* LSD-сортировка */

2014-05-22T06:18:55Z

‎LSD-сортировка

Smnikita: /* Сложность MSD-сортировки */

2014-05-20T19:09:32Z

‎Сложность MSD-сортировки

Smnikita: /* Сложность MSD-сортировки */

2014-05-20T19:05:23Z

‎Сложность MSD-сортировки

194.85.161.2 в 18:55, 20 мая 2014

2014-05-20T18:55:38Z

Shersh в 18:01, 20 мая 2014

2014-05-20T18:01:15Z

← Предыдущая		Версия 16:05, 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 Майкл Наки].
−	\|}
−
−

	'''Цифровая сортировка''' (англ. ''radix sort'') {{---}} один из алгоритмов сортировки, использующих внутреннюю структуру сортируемых объектов.		'''Цифровая сортировка''' (англ. ''radix sort'') {{---}} один из алгоритмов сортировки, использующих внутреннюю структуру сортируемых объектов.

← Предыдущая		Версия 06:30, 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 Майкл Наки].
		+	\|}
		+
		+

	'''Цифровая сортировка''' (англ. ''radix sort'') {{---}} один из алгоритмов сортировки, использующих внутреннюю структуру сортируемых объектов.		'''Цифровая сортировка''' (англ. ''radix sort'') {{---}} один из алгоритмов сортировки, использующих внутреннюю структуру сортируемых объектов.

@@ Строка 68: / Строка 68: @@
            j = digit(A[i], d)
            c[l + cnt[j]] = A[i]
-           cnt[j]++
+           cnt[j]--
        '''for''' i = l '''to''' r
            A[i] = c[i]

@@ Строка 1: / Строка 1: @@
-'''Цифровая сортировка'''  — один из алгоритмов сортировки, использующих внутреннюю структуру сортируемых объектов.
+'''Цифровая сортировка''' (англ. ''radix sort'') {{---}} один из алгоритмов сортировки, использующих внутреннюю структуру сортируемых объектов.
 == Алгоритм ==
 [[Файл:Цифровая_сортировка.png|thumb|right|450px|Пример цифровой сортировки трехзначных чисел, начиная с младших разрядов]]

← Предыдущая		Версия 17:03, 13 февраля 2015
Строка 100:		Строка 100:
	[[Категория: Дискретная математика и алгоритмы]]		[[Категория: Дискретная математика и алгоритмы]]
	[[Категория: Сортировки]]		[[Категория: Сортировки]]
		+	[[Категория: Другие сортировки]]

@@ Строка 28: / Строка 28: @@
 == Псевдокод ==
 === LSD-сортировка ===
-В качестве примера рассмотрим сортировку чисел. Как говорилось выше, в такой ситуации в качестве устойчивой сортировки применяют сортировку подсчетом, так как обычно количество различных значений разрядов не превосходит количества сортируемых элементов. Ниже приведен псевдокод цифровой сортировки, которой подается массив <tex> A </tex> <tex> m </tex>-разрядных чисел размера <tex> n </tex>. Сам по себе алгоритм представляет собой цикл по номеру разряда, на каждой итерации которого элементы массива <tex> A </tex> размещаются в нужном порядке во вспомогательном массиве <tex> B </tex>. Для подсчета количества объектов, <tex> i </tex>-й разряд которых одинаковый, а затем и для определения положения объектов в массиве <tex> B </tex> используется вспомогательный массив <tex> C </tex>. Функция <tex> \mathrm{digit(x, i)} </tex> возвращает <tex> i </tex>-й разряд числа <tex> x </tex>. Также считаем, что значения разрядов меньше <tex> k </tex>.
+В качестве примера рассмотрим сортировку чисел. Как говорилось выше, в такой ситуации в качестве устойчивой сортировки применяют сортировку подсчетом, так как обычно количество различных значений разрядов не превосходит количества сортируемых элементов. Ниже приведен псевдокод цифровой сортировки, которой подается массив <tex> A </tex> размера <tex> n </tex> <tex> m </tex>-разрядных чисел . Сам по себе алгоритм представляет собой цикл по номеру разряда, на каждой итерации которого элементы массива <tex> A </tex> размещаются в нужном порядке во вспомогательном массиве <tex> B </tex>. Для подсчета количества объектов, <tex> i </tex>-й разряд которых одинаковый, а затем и для определения положения объектов в массиве <tex> B </tex> используется вспомогательный массив <tex> C </tex>. Функция <tex> \mathrm{digit(x, i)} </tex> возвращает <tex> i </tex>-й разряд числа <tex> x </tex>. Также считаем, что значения разрядов меньше <tex> k </tex>.
    '''function''' radixSort(int[] A):
        '''for''' i = 1 '''to''' m

@@ Строка 85: / Строка 85: @@
 Пусть значения разрядов меньше <tex>b</tex>, а количество разрядов {{---}} <tex>k</tex>. При сортировке массива из одинаковых элементов MSD-сортировкой на каждом шаге все элементы будут находится в неубывающей по размеру корзине, а так как цикл идет по всем элементам массива, то получим, что время работы MSD-сортировки оценивается величиной <tex>O(nk)</tex>, причем это время нельзя улучшить. Хорошим случаем для данной сортировки будет массив, при котором на каждом шаге каждая корзина будет делиться на <tex>b</tex> частей. Как только размер корзины станет равен <tex>1</tex>, сортировка перестанет рекурсивно запускаться в этой корзине. Таким образом, асимптотика будет <math>\Omega(n\log_b{n})</math>. Это хорошо тем, что не зависит от числа разрядов.
-Существует так же модификация MSD-сортировки, при которой рекурсивный процесс останавливается при небольших размерах текущего кармана, и вызывается более быстрая сортировка, основанная на сравнениях (например, сортировка вставками).
+Существует также модификация MSD-сортировки, при которой рекурсивный процесс останавливается при небольших размерах текущего кармана, и вызывается более быстрая сортировка, основанная на сравнениях (например, сортировка вставками).
 == См. также ==

@@ Строка 55: / Строка 55: @@
 Изначально запускаем функцию так <math>\mathrm{radixSort(A, 0, A.length - 1, 1)}</math>
-   '''function''' radixSort(int[] A, int l, int r, int d)
+   '''function''' radixSort(int[] A, int l, int r, int d):
        '''if''' d > m '''or''' l >= r
            '''return'''
@@ Строка 83: / Строка 83: @@
 Если количество разрядов {{---}} константа, а <tex> k = O(n) </tex>, то сложность цифровой сортировки составляет <tex> O(n) </tex>, то есть она линейно зависит от количества сортируемых чисел.
 ===Сложность MSD-сортировки===
-Пусть значения разрядов меньше <tex>b</tex>, а количество разрядов {{---}} <tex>k</tex>. При сортировке массива из одинаковых элементов MSD-сортировкой на каждом шаге все элементы будут находится в неубывающей по размеру корзине, а так как цикл идет по всем элементам массива, то получим, что время работы MSD-сортировки оценивается величиной <tex>O(n \times k)</tex>, причем это время нельзя улучшить. Хорошим случаем для данной сортировки будем массив, при котором на каждом шаге каждая корзина будет делиться на b частей. Как только размер корзины станет равен <tex>1</tex>, то больше сортировка не будет рекурсивно запускаться в этой корзине. Таким образом, асимптотика будет <math>\Omega(n \times log_b{n})</math>. Это хорошо тем, что не зависит от числа разрядов.
+Пусть значения разрядов меньше <tex>b</tex>, а количество разрядов {{---}} <tex>k</tex>. При сортировке массива из одинаковых элементов MSD-сортировкой на каждом шаге все элементы будут находится в неубывающей по размеру корзине, а так как цикл идет по всем элементам массива, то получим, что время работы MSD-сортировки оценивается величиной <tex>O(nk)</tex>, причем это время нельзя улучшить. Хорошим случаем для данной сортировки будет массив, при котором на каждом шаге каждая корзина будет делиться на <tex>b</tex> частей. Как только размер корзины станет равен <tex>1</tex>, сортировка перестанет рекурсивно запускаться в этой корзине. Таким образом, асимптотика будет <math>\Omega(n\log_b{n})</math>. Это хорошо тем, что не зависит от числа разрядов.
-Существует так же модификация MSD-сортировки, при которой рекурсивный процесс останавливается при небольших размерах текущего кармана и вызывается более быстрая сортировка основанная на сравнениях (например, сортировка вставками).
+Существует так же модификация MSD-сортировки, при которой рекурсивный процесс останавливается при небольших размерах текущего кармана, и вызывается более быстрая сортировка основанная на сравнениях (например, сортировка вставками).
 == См. также ==

@@ Строка 86: / Строка 86: @@
 Существует так же модификация MSD-сортировки, при которой рекурсивный процесс останавливается при небольших размерах текущего кармана и вызывается более быстрая сортировка основанная на сравнениях (например, сортировка вставками).
 == Источники информации ==
@@ Строка 93: / Строка 97: @@
 * Дональд Кнут Искусство программирования, том 3. Сортировка и поиск
 * Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ
 [[Категория: Дискретная математика и алгоритмы]]
 [[Категория: Сортировки]]