Алгоритм цифровой сортировки - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:35:31Z

rollbackEdits.php mass rollback

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

2022-09-01T04:07:00Z

178.237.190.252: /* Алгоритм LSD */

2018-08-26T17:54:07Z

‎Алгоритм LSD

Nikita.Ofitserov в 15:39, 28 июня 2011

2011-06-28T15:39:41Z

Nikita.Ofitserov в 15:37, 28 июня 2011

2011-06-28T15:37:18Z

192.168.0.2 в 05:38, 7 июня 2011

2011-06-07T05:38:56Z

192.168.0.2 в 23:54, 16 мая 2011

2011-05-16T23:54:40Z

192.168.0.2 в 16:19, 11 мая 2011

2011-05-11T16:19:28Z

192.168.0.2 в 16:17, 11 мая 2011

2011-05-11T16:17:52Z

192.168.0.2 в 16:14, 11 мая 2011

2011-05-11T16:14:46Z

← Предыдущая		Версия 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 Майкл Наки].
−	\|}
−
	В этом алгоритме сортировки числа сортируются по разрядам. Существует два варианта Least Significant Digit (LSD) и Most Significant Digit (MSD). При LSD сортировке, сначала сортируются младшие разряды, затем старшие. При MSD сортировке наоборот.		В этом алгоритме сортировки числа сортируются по разрядам. Существует два варианта Least Significant Digit (LSD) и Most Significant Digit (MSD). При LSD сортировке, сначала сортируются младшие разряды, затем старшие. При MSD сортировке наоборот.

← Предыдущая		Версия 04:07, 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 Майкл Наки].
		+	\|}
		+
	В этом алгоритме сортировки числа сортируются по разрядам. Существует два варианта Least Significant Digit (LSD) и Most Significant Digit (MSD). При LSD сортировке, сначала сортируются младшие разряды, затем старшие. При MSD сортировке наоборот.		В этом алгоритме сортировки числа сортируются по разрядам. Существует два варианта Least Significant Digit (LSD) и Most Significant Digit (MSD). При LSD сортировке, сначала сортируются младшие разряды, затем старшие. При MSD сортировке наоборот.

@@ Строка 48: / Строка 48: @@
 <tex>list9: 98</tex>
-''Второй этап'' {{---}} собираем и получаем отсортированную по возрастанию последовательность: <tex>8, 9(list0), 11(list1), 21(list2), 59(list5), 76(list7), 98(list 9)</tex>
+''Второй этап'' {{---}} собираем и получаем отсортированную по возрастанию последовательность: <tex>8, 9(list0), 11(list1), 21, 24(list2), 59(list5), 76(list7), 98(list 9)</tex>
 == Время работы ==

@@ Строка 2: / Строка 2: @@
 == Алгоритм LSD==
 Перед сортировкой необходимо определить 2 величины:
@@ Строка 9: / Строка 7: @@
 # <tex>range</tex> {{---}} количество возможных значений одного разряда ключа (сортируемого элемента), то есть мощность используемого алфавита.
-Сам алгоритм работает следующим образом. Создаются <tex>range</tex> вспомогательных списков - корзин, т.е. на каждое возможное значение разряда элемента по корзине.
+Создаются <tex>range</tex> вспомогательных списков-корзин, т.е. на каждое возможное значение разряда элемента по корзине.
 '''Первый проход:'''
@@ Строка 27: / Строка 25: @@
 <tex>list9: 9, 59</tex>
-''Второй этап'' - сборка: просто последовательно соединяем один за другим все корзины и располагаем элементы уже в этой последовательности:
+''Второй этап'' {{---}} сборка: просто последовательно соединяем один за другим все корзины и располагаем элементы уже в этой последовательности:
 <tex>11, 21 (list1), 24(list4), 76(list6), 98, 8(list8), 9, 59(list9)</tex>

@@ Строка 6: / Строка 6: @@
 Перед сортировкой необходимо определить 2 величины:
-<tex>1. width</tex> - максимальное количество разрядов в сортируемых величинах.
+# <tex>width</tex> {{---}} максимальное количество разрядов в сортируемых величинах.
+# <tex>range</tex> {{---}} количество возможных значений одного разряда ключа (сортируемого элемента), то есть мощность используемого алфавита.
 Сам алгоритм работает следующим образом. Создаются <tex>range</tex> вспомогательных списков - корзин, т.е. на каждое возможное значение разряда элемента по корзине.
@@ Строка 14: / Строка 13: @@
 '''Первый проход:'''
-''Первый этап'' - распределение по корзинам и на первом проходе элементы исходной последовательности помещаются в эти корзины по их младшему разряду, т.е. по самому правому символу. Какой этот самый младший разряд у элемента, в такую корзину этот элемент и помещается.
+''Первый этап'' {{---}} распределение по корзинам и на первом проходе элементы исходной последовательности помещаются в эти корзины по их младшему разряду, т.е. по самому правому символу. Какой этот самый младший разряд у элемента, в такую корзину этот элемент и помещается.
 Например, пусть имеем исходную последовательность из <tex>{11, 24, 9, 59, 21, 98, 76, 8}</tex>, для которой определяем <tex>width</tex> = 2, <tex>range</tex> = 10, поэтому будет 10 корзин: <tex>list0, list1..., list9</tex>. Тогда на первом проходе корзины №0, 2, 3, 5, 7 окажутся пусты, а остальные распределят элементы след. образом:
@@ Строка 37: / Строка 36: @@
 '''Второй проход:'''
-''Первый этап'' - корзины №3, 4, 6, 8 окажутся пусты, а остальные распределят элементы след. образом:
+''Первый этап'' {{---}} корзины №3, 4, 6, 8 окажутся пусты, а остальные распределят элементы след. образом:
 <tex>list0: 8, 9</tex>
@@ Строка 51: / Строка 50: @@
 <tex>list9: 98</tex>
-''Второй этап'' - собираем и получаем отсортированную по возрастанию последовательность: <tex>8, 9(list0), 11(list1), 21(list2), 59(list5), 76(list7), 98(list 9)</tex>
+''Второй этап'' {{---}} собираем и получаем отсортированную по возрастанию последовательность: <tex>8, 9(list0), 11(list1), 21(list2), 59(list5), 76(list7), 98(list 9)</tex>
 == Время работы ==
-Алгоритм цифровой сортировки работает за линейное время - <tex>O(k(n + |A|))</tex>, где <tex>|A|</tex> - мощность алфавита(<tex>range</tex>), <tex>k</tex> - максимальная длина строки(<tex>width</tex>), <tex>n</tex> - количество сортируемых строк.
+Алгоритм цифровой сортировки работает за линейное время - <tex>O(k(n + |A|))</tex>, где <tex>|A|</tex> {{---}} мощность алфавита(<tex>range</tex>), <tex>k</tex> {{---}} максимальная длина строки(<tex>width</tex>), <tex>n</tex> {{---}} количество сортируемых строк.
 == Применение ==
-Алгоритм цифровой сортировки позволяет строить суффиксный массив за <tex>O(n^2)</tex>, где <tex>n</tex> - длина строки.
+Алгоритм цифровой сортировки позволяет строить суффиксный массив за <tex>O(n^2)</tex>, где <tex>n</tex> {{---}} длина строки.
 == Источник ==
 Дональд Кнут Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е изд. — М.: «Вильямс», 2007. — С. 824. — ISBN 5-8459-0082-4

← Предыдущая		Версия 05:38, 7 июня 2011
Строка 1:		Строка 1:
−	В этом алгоритме сортировки числа сортируются по разрядам. Существует два варианта ~~least significant digit~~ (LSD) и ~~most significant digit~~ (MSD). При LSD сортировке, сначала сортируются младшие разряды, затем старшие. При MSD сортировке наоборот.	+	В этом алгоритме сортировки числа сортируются по разрядам. Существует два варианта Least Significant Digit (LSD) и Most Significant Digit (MSD). При LSD сортировке, сначала сортируются младшие разряды, затем старшие. При MSD сортировке наоборот.

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

← Предыдущая		Версия 23:54, 16 мая 2011
Строка 1:		Строка 1:
−	В этом алгоритме сортировки числа сортируются по разрядам. Существует два варианта least significant digit (LSD) и most significant digit (MSD). При LSD сортировке, сначала сортируются младшие разряды, затем старшие. При MSD сортировке ~~все~~ наоборот.	+	В этом алгоритме сортировки числа сортируются по разрядам. Существует два варианта least significant digit (LSD) и most significant digit (MSD). При LSD сортировке, сначала сортируются младшие разряды, затем старшие. При MSD сортировке наоборот.

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

@@ Строка 14: / Строка 14: @@
 '''Первый проход:'''
-Первый этап распределение по корзинам и на первом проходе элементы исходной последовательности помещаются в эти корзины по их младшему разряду, т.е. по самому правому символу. Какой этот самый младший разряд у элемента, в такую корзину этот элемент и помещается.
+''Первый этап'' распределение по корзинам и на первом проходе элементы исходной последовательности помещаются в эти корзины по их младшему разряду, т.е. по самому правому символу. Какой этот самый младший разряд у элемента, в такую корзину этот элемент и помещается.
 Например, пусть имеем исходную последовательность из <tex>{11, 24, 9, 59, 21, 98, 76, 8}</tex>, для которой определяем <tex>width</tex> = 2, <tex>range</tex> = 10, поэтому будет 10 корзин: <tex>list0, list1..., list9</tex>. Тогда на первом проходе корзины №0, 2, 3, 5, 7 окажутся пусты, а остальные распределят элементы след. образом:
@@ Строка 28: / Строка 28: @@
 <tex>list9: 9, 59</tex>
-'''Второй этап''' - сборка: просто последовательно соединяем один за другим все корзины и располагаем элементы уже в этой последовательности:
+''Второй этап'' - сборка: просто последовательно соединяем один за другим все корзины и располагаем элементы уже в этой последовательности:
 <tex>11, 21 (list1), 24(list4), 76(list6), 98, 8(list8), 9, 59(list9)</tex>
@@ Строка 37: / Строка 37: @@
 '''Второй проход:'''
-На втором проходе корзины №3, 4, 6, 8 окажутся пусты, а остальные распределят элементы след. образом:
+На ''первом этапе'' корзины №3, 4, 6, 8 окажутся пусты, а остальные распределят элементы след. образом:
 <tex>list0: 8, 9</tex>
@@ Строка 51: / Строка 51: @@
 <tex>list9: 98</tex>
-Собираем и получаем отсортированную по возрастанию последовательность: <tex>8, 9(list0), 11(list1), 21(list2), 59(list5), 76(list7), 98(list 9)</tex>
+''На втором этапе'' собираем и получаем отсортированную по возрастанию последовательность: <tex>8, 9(list0), 11(list1), 21(list2), 59(list5), 76(list7), 98(list 9)</tex>

@@ Строка 12: / Строка 12: @@
 Сам алгоритм работает следующим образом. Создаются <tex>range</tex> вспомогательных списков - корзин, т.е. на каждое возможное значение разряда элемента по корзине.
-'''Первый этап''' распределение по корзинам и на первом проходе элементы исходной последовательности помещаются в эти корзины по их младшему разряду, т.е. по самому правому символу. Какой этот самый младший разряд у элемента, в такую корзину этот элемент и помещается.
+'''Первый проход:'''
-Например, пусть имеем исходную последовательность из <tex>{11, 24, 9, 59, 21, 98, 76, 8}</tex>, для которой определяем <tex>width</tex> = 2, <tex>range</tex> = 10, поэтому будет 10 корзин: <tex>list0, list1..., list9</tex>. Тогда на первом проходе корзины №2, 3, 5, 7 окажутся пусты, а остальные распределят элементы след. образом:
+Первый этап распределение по корзинам и на первом проходе элементы исходной последовательности помещаются в эти корзины по их младшему разряду, т.е. по самому правому символу. Какой этот самый младший разряд у элемента, в такую корзину этот элемент и помещается.
-<tex>list0: 9, 8</tex>
+Например, пусть имеем исходную последовательность из <tex>{11, 24, 9, 59, 21, 98, 76, 8}</tex>, для которой определяем <tex>width</tex> = 2, <tex>range</tex> = 10, поэтому будет 10 корзин: <tex>list0, list1..., list9</tex>. Тогда на первом проходе корзины №0, 2, 3, 5, 7 окажутся пусты, а остальные распределят элементы след. образом:
 <tex>list1: 11, 21</tex>
@@ Строка 24: / Строка 24: @@
 <tex>list6: 76</tex>
-<tex>list8: 98</tex>
+<tex>list8: 98, 8</tex>
-<tex>list9: 59</tex>
+<tex>list9: 9, 59</tex>
 '''Второй этап''' - сборка: просто последовательно соединяем один за другим все корзины и располагаем элементы уже в этой последовательности:
-<tex>9, 8 (list0), 11, 21 (list1), 24(list4), 76(list6), 98(list8), 59(list9)</tex>
+<tex>11, 21 (list1), 24(list4), 76(list6), 98, 8(list8), 9, 59(list9)</tex>
 Это был один проход алгоритма, соответствующий крайнему правому разряду ключа.
 На следующем проходе, элементы из уже обновленной последовательности распределяются по корзинам в соответствии с их вторым(т.е. предпоследним) разрядом и т.д по самого старшего, максимального, <tex>width</tex>-го разряда ключа.
 == Время работы ==