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

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:03:40Z

rollbackEdits.php mass rollback

185.243.218.46 в 06:37, 1 сентября 2022

2022-09-01T06:37:19Z

95.58.179.186: /* Реализация */

2019-10-28T11:34:52Z

‎Реализация

Дмитрий Мурзин в 12:33, 16 января 2019

2019-01-16T12:33:53Z

Shersh: /* Сложность */

2015-04-16T16:51:46Z

‎Сложность

Shersh: /* JSort */

2015-03-25T11:00:33Z

‎JSort

Flanir1: /* Пример */

2015-03-21T14:47:21Z

‎Пример

Flanir1: /* Пример */

2015-03-21T14:46:15Z

‎Пример

Flanir1: /* Сложность */

2015-03-21T14:45:51Z

‎Сложность

Flanir1: /* Сложность */

2015-03-21T14:44:24Z

‎Сложность

← Предыдущая		Версия 16:03, 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 Майкл Наки].
−	\|}
−
	'''Сортировка кучей''', '''пирамидальная сортировка''' (англ. ''Heapsort'') {{---}} алгоритм сортировки, использующий структуру данных [[Двоичная куча\|двоичная куча]]. Это неустойчивый алгоритм сортировки с временем работы <tex>O(n\log{n})</tex> , где <tex>n</tex> {{---}} количество элементов для сортировки, и использующий <tex>O(1)</tex> дополнительной памяти.		'''Сортировка кучей''', '''пирамидальная сортировка''' (англ. ''Heapsort'') {{---}} алгоритм сортировки, использующий структуру данных [[Двоичная куча\|двоичная куча]]. Это неустойчивый алгоритм сортировки с временем работы <tex>O(n\log{n})</tex> , где <tex>n</tex> {{---}} количество элементов для сортировки, и использующий <tex>O(1)</tex> дополнительной памяти.

← Предыдущая		Версия 06:37, 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 Майкл Наки].
		+	\|}
		+
	'''Сортировка кучей''', '''пирамидальная сортировка''' (англ. ''Heapsort'') {{---}} алгоритм сортировки, использующий структуру данных [[Двоичная куча\|двоичная куча]]. Это неустойчивый алгоритм сортировки с временем работы <tex>O(n\log{n})</tex> , где <tex>n</tex> {{---}} количество элементов для сортировки, и использующий <tex>O(1)</tex> дополнительной памяти.		'''Сортировка кучей''', '''пирамидальная сортировка''' (англ. ''Heapsort'') {{---}} алгоритм сортировки, использующий структуру данных [[Двоичная куча\|двоичная куча]]. Это неустойчивый алгоритм сортировки с временем работы <tex>O(n\log{n})</tex> , где <tex>n</tex> {{---}} количество элементов для сортировки, и использующий <tex>O(1)</tex> дополнительной памяти.

@@ Строка 12: / Строка 12: @@
      buildHeap(A)
      heapSize = A.size
-     '''for''' i = 0 '''to''' n - 2
+     '''for''' i = 0 '''to''' n - 1
        swap(A[0], A[n - 1 - i])
        heapSize--

@@ Строка 2: / Строка 2: @@
 == Алгоритм ==
-Необходимо отсортировать массив <tex>A</tex>, размером <tex>n</tex>. Построим на базе этого массива за <tex>O(n)</tex> кучу для максимума. Так как максимальный элемент находится в корне, то,если поменять его местами с <tex>A[n - 1]</tex>, он встанет на свое место. Далее вызовем процедуру <tex> \mathrm{siftDown(0)} </tex>, предварительно уменьшив <tex> \mathrm{heapSize} </tex> на <tex>1</tex>. Она за <tex>O(\log{n})</tex> просеет <tex>A[0]</tex> на нужное место и сформирует новую кучу (так как мы уменьшили ее размер, то куча располагается с <tex>A[0]</tex> по <tex>A[n - 2]</tex>, а элемент <tex>A[n-1]</tex> находится на своем месте). Повторим эту процедуру для новой кучи, только корень будет менять местами не с <tex>A[n - 1]</tex>, а с <tex>A[n-2]</tex>. Делая аналогичные действия, пока <tex> \mathrm{heapSize}  </tex> не станет равен <tex>1</tex>, мы будем ставить наибольшее из оставшихся чисел в конец не отсортированной части. Очевидно, что таким образом, мы получим отсортированный массив.
+Необходимо отсортировать массив <tex>A</tex>, размером <tex>n</tex>. Построим на базе этого массива за <tex>O(n)</tex> кучу для максимума. Так как максимальный элемент находится в корне, то если поменять его местами с <tex>A[n - 1]</tex>, он встанет на своё место. Далее вызовем процедуру <tex> \mathrm{siftDown(0)} </tex>, предварительно уменьшив <tex> \mathrm{heapSize} </tex> на <tex>1</tex>. Она за <tex>O(\log{n})</tex> просеет <tex>A[0]</tex> на нужное место и сформирует новую кучу (так как мы уменьшили её размер, то куча располагается с <tex>A[0]</tex> по <tex>A[n - 2]</tex>, а элемент <tex>A[n-1]</tex> находится на своём месте). Повторим эту процедуру для новой кучи, только корень будет менять местами не с <tex>A[n - 1]</tex>, а с <tex>A[n-2]</tex>. Делая аналогичные действия, пока <tex> \mathrm{heapSize}  </tex> не станет равен <tex>1</tex>, мы будем ставить наибольшее из оставшихся чисел в конец не отсортированной части. Очевидно, что таким образом, мы получим отсортированный массив.
 == Реализация ==
 *<tex>\mathrm{A}</tex> {{---}} массив, который необходимо отсортировать
-*<tex>\mathrm{n}</tex> {{---}} количество элементов в нем
+*<tex>\mathrm{n}</tex> {{---}} количество элементов в нём
 *<tex> \mathrm{buildHeap(A)} </tex> {{---}} процедура, которая строит из передаваемого массива кучу для максимума в этом же массиве
 *<tex> \mathrm{siftDown(A, i, len)} </tex> {{---}} процедура, которая просеивает вниз элемент <tex> \mathrm{A[i]} </tex> в куче из <tex> \mathrm{len} </tex> элементов, находящихся в начале массива <tex> \mathrm{A} </tex>
@@ Строка 37: / Строка 37: @@
   |[[Файл:heap4.png|155px|thumb|Второй проход]]
   |[[Файл:heap5.png|155px|thumb|Третий проход]]
-  |[[Файл:heap6.png|155px|thumb|Четвертый проход]]
+  |[[Файл:heap6.png|155px|thumb|Четвёртый проход]]
   |}
@@ Строка 55: / Строка 55: @@
 |-
 |style="background-color:#FFF;padding:2px 10px"| '''4''' 3 2 1 5
-|style="background-color:#FFF;padding:2px 10px"| Строим кучу из первых четырех элементов
+|style="background-color:#FFF;padding:2px 10px"| Строим кучу из первых четырёх элементов
 |-
 |colspan=3|''Второй проход''
 |-
 |style="background-color:#FFF;padding:2px 10px"| '''1''' 3 2 '''4''' 5
-|style="background-color:#FFF;padding:2px 10px"| Меняем местами первый и четвертый элементы
+|style="background-color:#FFF;padding:2px 10px"| Меняем местами первый и четвёртый элементы
 |-
 |style="background-color:#FFF;padding:2px 10px"| '''3''' 1 2 4 5
-|style="background-color:#FFF;padding:2px 10px"| Строим кучу из первых трех элементов
+|style="background-color:#FFF;padding:2px 10px"| Строим кучу из первых трёх элементов
 |-
 |colspan=3|''Третий проход''
@@ Строка 73: / Строка 73: @@
 |style="background-color:#FFF;padding:2px 10px"| Строим кучу из двух элементов
 |-
-|colspan=3|''Четвертый проход''
+|colspan=3|''Четвёртый проход''
 |-
 |style="background-color:#FFF;padding:2px 10px"| '''1''' '''2''' 3 4 5
@@ Строка 87: / Строка 87: @@
 = JSort =
 '''JSort''' является модификацией сортировки кучей, которую придумал Джейсон Моррисон (''Jason Morrison'').
-Алгоритм частично упорядочивает массив, строя на нем два раза кучу: один раз передвигая меньшие элементы влево, второй раз передвигая большие элементы вправо. Затем к массиву применяется
+Алгоритм частично упорядочивает массив, строя на нём два раза кучу: один раз передвигая меньшие элементы влево, второй раз передвигая большие элементы вправо. Затем к массиву применяется
 [[Сортировка вставками|сортировка вставками]], которая при почти отсортированных данных работает за <tex>O(n)</tex>.
@@ Строка 99: / Строка 99: @@
 Построим кучу для минимума на этом массиве.
 Тогда наименьший элемент окажется на первой позиции, а левая часть массива окажется почти отсортированной, так как ей будут соответствовать верхние узлы кучи.
-Теперь построим на этом же массиве кучу так, чтобы немного упорядочить правую часть массива. Эта куча должна быть кучей для максимума и быть "зеркальной" к массиву, то есть чтобы ее корень соответствовал последнему элементу массива.
+Теперь построим на этом же массиве кучу так, чтобы немного упорядочить правую часть массива. Эта куча должна быть кучей для максимума и быть "зеркальной" к массиву, то есть чтобы её корень соответствовал последнему элементу массива.
 К получившемуся массиву применим сортировку вставками.

@@ Строка 104: / Строка 104: @@
 === Сложность ===
-Постройка кучи занимает <tex>O(n)</tex>. Почти упорядоченный массив сортировка вставками может отсортировать <tex> O(n)</tex>, но в худшем случае за <tex>O(n^2)</tex>.
+Построение кучи занимает <tex>O(n)</tex>. Почти упорядоченный массив сортировка вставками может отсортировать <tex> O(n)</tex>, но в худшем случае за <tex>O(n^2)</tex>.
 Таким образом, наихудшая оценка Jsort {{---}} <tex>O(n^2)</tex>.

@@ Строка 91: / Строка 91: @@
 Достоинства:
-*В отличии от сортировки кучей, на почти отсортированных массивах работает быстрее, чем на случайных.
+*В отличие от сортировки кучей, на почти отсортированных массивах работает быстрее, чем на случайных.
 *В силу использования сортировки вставками, которая просматривает элементы последовательно, использование кэша гораздо эффективнее.
 Недостатки:

@@ Строка 115: / Строка 115: @@
 | [[Файл:HeapW.png|400px]]
 |}
-Сам массив же будет выглядеть следующим образом:
+Массив выглядит следующим образом:
 {| cellpadding="3" style="margin-left: left; margin-right: left;"
 | [[Файл:HeapM.png|400px]]

@@ Строка 125: / Строка 125: @@
 | [[Файл:HeapWU.png|400px]]
 |}
-Сам массив же будет выглядеть следующим образом:
+Массив будет выглядеть следующим образом:
 {| cellpadding="3" style="margin-left: left; margin-right: left;"
 | [[Файл:HeapMU.png|400px]]

@@ Строка 106: / Строка 106: @@
 Постройка кучи занимает <tex>O(n)</tex>. Почти упорядоченный массив сортировка вставками может отсортировать <tex> O(n)</tex>, но в худшем случае за <tex>O(n^2)</tex>.
-Таким образом в худшем случае сложность JSort является <tex>O(n^2)</tex>.
+Таким образом, наихудшая оценка Jsort {{---}} <tex>O(n^2)</tex>
 === Пример ===