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

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:15:26Z

rollbackEdits.php mass rollback

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

2022-09-01T05:53:00Z

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

2015-09-24T18:55:41Z

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

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

2015-02-13T16:45:32Z

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

AlexeyL в 15:49, 12 июня 2014

2014-06-12T15:49:13Z

AlexeyL в 15:41, 12 июня 2014

2014-06-12T15:41:28Z

Shersh: /* Алгоритм */

2014-06-12T15:32:03Z

‎Алгоритм

AlexeyL в 13:40, 12 июня 2014

2014-06-12T13:40:29Z

AlexeyL: /* Алгоритм */

2014-06-12T13:32:26Z

‎Алгоритм

Shersh: /* Анализ */

2014-06-12T10:04:51Z

‎Анализ

← Предыдущая		Версия 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 Майкл Наки].
−	\|}
−
	== Описание ==		== Описание ==
	Parallel Sorting by Regular Sampling {{---}} параллельная сортировка, разработанная Ханмао Ши, Рисажем Канселом и Джонатаном Шеффером в 1992 году. Имеет два преимущества по сравнению с [[Быстрая сортировка\|быстрой сортировкой]]:		Parallel Sorting by Regular Sampling {{---}} параллельная сортировка, разработанная Ханмао Ши, Рисажем Канселом и Джонатаном Шеффером в 1992 году. Имеет два преимущества по сравнению с [[Быстрая сортировка\|быстрой сортировкой]]:

← Предыдущая		Версия 05:53, 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 Майкл Наки].
		+	\|}
		+
	== Описание ==		== Описание ==
	Parallel Sorting by Regular Sampling {{---}} параллельная сортировка, разработанная Ханмао Ши, Рисажем Канселом и Джонатаном Шеффером в 1992 году. Имеет два преимущества по сравнению с [[Быстрая сортировка\|быстрой сортировкой]]:		Parallel Sorting by Regular Sampling {{---}} параллельная сортировка, разработанная Ханмао Ши, Рисажем Канселом и Джонатаном Шеффером в 1992 году. Имеет два преимущества по сравнению с [[Быстрая сортировка\|быстрой сортировкой]]:

← Предыдущая		Версия 18:55, 24 сентября 2015
Строка 130:		Строка 130:
	[[Категория:Дискретная математика и алгоритмы]]		[[Категория:Дискретная математика и алгоритмы]]
	[[Категория:Сортировка]]		[[Категория:Сортировка]]
		+	[[Категория: Многопоточные сортировки]]

@@ Строка 124: / Строка 124: @@
 * [[Многопоточная сортировка слиянием|Многопоточная сортировка слиянием]]
 * [[Быстрая сортировка|Быстрая сортировка]]
-= Источники информации =
+== Источники информации ==
 * [https://wiki.engr.illinois.edu/download/attachments/99155993/Sort+ParaProg(Quinn)chpt14.5.pdf?version=1&modificationDate=1203641170000| Статья о PSRS]
 * [http://users.cms.caltech.edu/~cs284/lectures/29oct97/sld003.htm| Презентация]

@@ Строка 1: / Строка 1: @@
-= Описание =
+== Описание ==
 Parallel Sorting by Regular Sampling {{---}} параллельная сортировка, разработанная Ханмао Ши, Рисажем Канселом и Джонатаном Шеффером в 1992 году. Имеет два преимущества по сравнению с [[Быстрая сортировка|быстрой сортировкой]]:
 * сохраняет размер списка более сбалансированным на протяжении всего процесса
 * избегает повторных перестановок ключей
-= Алгоритм =
+== Алгоритм ==
 * Начало.
 * '''Шаг 1.''' Исходный массив в <tex>n</tex> элементов разделим поровну между <tex>p</tex> процессорами.
@@ Строка 16: / Строка 16: @@
 * Конец.
-= Пример =
+== Пример ==
 Количество элементов <tex>27</tex>, количество процессоров <tex>3</tex>.
 Исходный набор данных:
@@ Строка 108: / Строка 108: @@
 |}
-= Анализ =
+== Анализ ==
 При <tex>n</tex> элементах и <tex>p</tex> процессорах начальная сортировка выполнится за <tex dpi=145>O( \frac {n\log(n/p)}{p})</tex>. Выбор порядка <tex>p</tex> элементов в каждом процессоре произойдёт за <tex>O(p)</tex>, их сортировать мы будем с помощью [[Быстрая сортировка|быстрой сортировки]], а так же учитывая, что их количество порядка <tex>p</tex>, то можно сказать, что они сортируются за <tex>O(p^2\log(p^2))=O(p^2\log(p))</tex>.
@@ Строка 121: / Строка 121: @@
 <tex dpi=145>O(\frac {n\log(n/p)}{p}+p^2\log(p)+n+p)=O(\frac {n\log(n/p)}{p})</tex>.
-= См. также =
+== См. также ==
 * [[Многопоточная сортировка слиянием|Многопоточная сортировка слиянием]]
 * [[Быстрая сортировка|Быстрая сортировка]]

@@ Строка 6: / Строка 6: @@
 == Алгоритм ==
 * Начало.
-* '''Шаг 1''' Исходный массив в <tex>n</tex> элементов разделим поровну между <tex>p</tex> процессорами.
+* '''Шаг 1.''' Исходный массив в <tex>n</tex> элементов разделим поровну между <tex>p</tex> процессорами.
 * '''Шаг 2''' На каждом процессоре запускам [[Быстрая сортировка|быструю сортировку]].
 * '''Шаг 3''' Формируем вспомогательный массив из элементов каждого процессора под индексами <tex dpi=145>0,\frac {n}  {p^2}, \frac {2n}{p^2},...,\frac {(p-1)n}{p^2}</tex>.

@@ Строка 111: / Строка 111: @@
 При <tex>n</tex> элементах и <tex>p</tex> процессорах начальная сортировка выполнится за <tex dpi=145>O( \frac {n\log(n/p)}{p})</tex>. Выбор порядка <tex>p</tex> элементов в каждом процессоре произойдёт за <tex>O(p)</tex>, их сортировать мы будем с помощью [[Быстрая сортировка|быстрой сортировки]], а так же учитывая, что их количество порядка <tex>p</tex>, то можно сказать, что они сортируются за <tex>O(p^2\log(p^2))=O(p^2\log(p))</tex>.
-После обмена данными будет произведено слияние <tex>p</tex> массивов в каждом процессоре. Также мы должны помнить, что при равномерном распределении данных длина сливаемых массивов будет <tex dpi=145>\frac {n}{p^2}</tex>, а <tex>\mathrm {merge} </tex> двух массивов выполняется за сумму их длин. Поэтому <tex>\mathrm {merge} </tex> займёт <tex dpi=145> O(\sum \limits_{k=2}^{p} \frac {k \cdot n}{p^2})=O(\frac {n \cdot p \cdot (p+1)}{2p^2}-\frac {n}{p^2})=O(n)</tex>.  <br>
+После обмена данными будет произведено слияние <tex>p</tex> массивов в каждом процессоре. Также мы должны помнить, что при равномерном распределении данных длина сливаемых массивов будет <tex dpi=145>\frac {n}{p^2}</tex>, а <tex>\mathrm {merge} </tex> двух массивов выполняется за сумму их длин. Поэтому <tex>\mathrm {merge} </tex> займёт <tex dpi=145> O(\sum \limits_{k=2}^{p} \frac {k \cdot n}{p^2})=O(\frac {n \cdot p \cdot (p+1)}{2p^2}-\frac {n}{p^2})=O(n)</tex>.
 Откуда получаем итоговую асимптотику:
-<tex dpi=145> O(\frac {n\log(n/p)}{p})+O(p^2\log(p))+O(n)+O(p)</tex> <br>
+<tex dpi=145> O(\frac {n\log(n/p)}{p})+O(p^2\log(p))+O(n)+O(p)</tex>
-Что равно: <br>
 <tex dpi=145>O(\frac {n\log(n/p)}{p}+p^2\log(p)+n+p)=O(\frac {n\log(n/p)}{p})</tex>.
@@ Строка 121: / Строка 124: @@
 * [[Многопоточная сортировка слиянием|Многопоточная сортировка слиянием]]
 * [[Быстрая сортировка|Быстрая сортировка]]
-* [[wikipedia:ru:Сортировка слиянием|Сортировка слиянием {{---}} Википедия]]
+== Источники информации ==
-* [[wikipedia:ru:Быстрая сортировка|Быстрая сортировка {{---}} Википедия]]
+* [https://wiki.engr.illinois.edu/download/attachments/99155993/Sort+ParaProg(Quinn)chpt14.5.pdf?version=1&modificationDate=1203641170000| Статья о PSRS]
 [[Категория:Дискретная математика и алгоритмы]]
 [[Категория:Сортировка]]