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

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:25:46Z

rollbackEdits.php mass rollback

103.251.167.21 в 04:59, 1 сентября 2022

2022-09-01T04:59:01Z

Cooleck: /* Разбиение массива */

2021-05-25T19:51:46Z

‎Разбиение массива

Cooleck: Если инкремировать и декремировать указатели после swap, то алгоритм будет падать на таком тесте a = [1, 2, 3, 4, 5, 6, -1, -2, 7, -4, -5]

2021-05-25T19:02:05Z

Если инкремировать и декремировать указатели после swap, то алгоритм будет падать на таком тесте a = [1, 2, 3, 4, 5, 6, -1, -2, 7, -4, -5]

81.89.176.166: /* Способ построить массив с максимальным количеством сравнений при детерминированном выборе опорного элемента */

2019-09-30T20:46:08Z

‎Способ построить массив с максимальным количеством сравнений при детерминированном выборе опорного элемента

Quasiyoke: /* Нерекурсивная реализация быстрой сортировки */ Исправил ошибку в описании модификации сортировки

2019-01-11T00:33:36Z

‎Нерекурсивная реализация быстрой сортировки: Исправил ошибку в описании модификации сортировки

93.175.2.28: /* Среднее время работы */

2018-06-22T10:24:09Z

‎Среднее время работы

188.130.155.157: /* Нерекурсивная реализация быстрой сортировки */ {{mxt|l}} перепутали с {{mxt|1}}

2018-04-03T18:12:44Z

‎Нерекурсивная реализация быстрой сортировки: {{mxt|l}} перепутали с {{mxt|1}}

212.13.112.162: /* Способ построить массив с максимальным количеством сравнений при детерминированном выборе опорного элемента */

2018-03-29T18:53:07Z

E-Maxon: Сортировка была не рабочая. Я исправил это и убрал лишнее.

2018-03-20T16:51:12Z

Сортировка была не рабочая. Я исправил это и убрал лишнее.

← Предыдущая		Версия 16:25, 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 Майкл Наки].
−	\|}
−
	'''Быстрая сортировка''' (англ. ''quick sort'', сортировка Хоара) {{---}} один из самых известных и широко используемых алгоритмов сортировки. Среднее время работы <Tex>O(n\log{n})</Tex>, что является асимптотически оптимальным временем работы для алгоритма, основанного на сравнении. Хотя время работы алгоритма для массива из <tex>n</tex> элементов в худшем случае может составить <tex>\Theta(n^2)</tex>, на практике этот алгоритм является одним из самых быстрых.		'''Быстрая сортировка''' (англ. ''quick sort'', сортировка Хоара) {{---}} один из самых известных и широко используемых алгоритмов сортировки. Среднее время работы <Tex>O(n\log{n})</Tex>, что является асимптотически оптимальным временем работы для алгоритма, основанного на сравнении. Хотя время работы алгоритма для массива из <tex>n</tex> элементов в худшем случае может составить <tex>\Theta(n^2)</tex>, на практике этот алгоритм является одним из самых быстрых.

← Предыдущая		Версия 04:59, 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 Майкл Наки].
		+	\|}
		+
	'''Быстрая сортировка''' (англ. ''quick sort'', сортировка Хоара) {{---}} один из самых известных и широко используемых алгоритмов сортировки. Среднее время работы <Tex>O(n\log{n})</Tex>, что является асимптотически оптимальным временем работы для алгоритма, основанного на сравнении. Хотя время работы алгоритма для массива из <tex>n</tex> элементов в худшем случае может составить <tex>\Theta(n^2)</tex>, на практике этот алгоритм является одним из самых быстрых.		'''Быстрая сортировка''' (англ. ''quick sort'', сортировка Хоара) {{---}} один из самых известных и широко используемых алгоритмов сортировки. Среднее время работы <Tex>O(n\log{n})</Tex>, что является асимптотически оптимальным временем работы для алгоритма, основанного на сравнении. Хотя время работы алгоритма для массива из <tex>n</tex> элементов в худшем случае может составить <tex>\Theta(n^2)</tex>, на практике этот алгоритм является одним из самых быстрых.

@@ Строка 33: / Строка 33: @@
           '''if''' (i <tex> \geqslant </tex> j)
              '''break'''
-          swap(a[i], a[j])
+          swap(a[i++], a[j--])
        '''return''' j

@@ Строка 33: / Строка 33: @@
           '''if''' (i <tex> \geqslant </tex> j)
              '''break'''
-          swap(a[i++], a[j--])
+          swap(a[i], a[j])
        '''return''' j

@@ Строка 107: / Строка 107: @@
 </center>
-Покажем, почему на данном массиве будет достигаться максимальное время работы быстрой сортировки. На этапе построения мы каждый раз присваивали опорному элементу минимальное значение. Следовательно, при выполнении <tex>\mathrm{quicksort}</tex> алгоритм в качестве опорного всегда будет выбирать наибольший элемент массива (выборка будет производится в том же порядке ввиду детерминированности определения опорного элемента).
+Покажем, почему на данном массиве будет достигаться максимальное время работы быстрой сортировки. На этапе построения мы каждый раз присваивали опорному элементу максимальное значение. Следовательно, при выполнении <tex>\mathrm{quicksort}</tex> алгоритм в качестве опорного всегда будет выбирать наибольший элемент массива (выборка будет производится в том же порядке ввиду детерминированности определения опорного элемента).
 Таким образом, так как каждый раз массив разбивается на две части {{---}} большие или равные опорному элементы и меньшие его {{---}} на каждом шаге имеем разбиение на массивы длины <tex>1</tex> и <tex>n-1</tex>, чего мы, собственно, и добивались. При таком выполнении алгоритма происходит <tex>\Theta(n^2)</tex> разделений на два подмассива, и на каждом разделении выполняется <tex>\Theta(n^2)</tex> сравнений.
 Следовательно, на данном массиве быстрая сортировка работает за <tex>\Theta(n^2)</tex>.

@@ Строка 161: / Строка 161: @@
              s.push(l, i - 1)
-В качестве альтернативного варианта можно использовать обычную рекурсивную версию, в которой вместо того, чтобы после разделения массива вызывать рекурсивно процедуру разделения для обоих найденных подмассивов, рекурсивный вызов делается только для меньшего подмассива, а больший обрабатывается в цикле в пределах этого же вызова процедуры. С точки зрения эффективности в среднем случае разницы практически нет: накладные расходы на дополнительный рекурсивный вызов и на организацию сравнения длин подмассивов и цикла — примерно одного порядка. Зато глубина рекурсии ни при каких обстоятельствах не превысит <tex>\log n</tex>, а в худшем случае вырожденного разделения она вообще будет не более <tex> n </tex> — вся обработка пройдёт в цикле первого уровня рекурсии.
+В качестве альтернативного варианта можно использовать обычную рекурсивную версию, в которой вместо того, чтобы после разделения массива вызывать рекурсивно процедуру разделения для обоих найденных подмассивов, рекурсивный вызов делается только для меньшего подмассива, а больший обрабатывается в цикле в пределах этого же вызова процедуры. С точки зрения эффективности в среднем случае разницы практически нет: накладные расходы на дополнительный рекурсивный вызов и на организацию сравнения длин подмассивов и цикла — примерно одного порядка. Зато глубина рекурсии ни при каких обстоятельствах не превысит <tex>\log n</tex>, а в худшем случае вырожденного разделения она вообще будет не более <tex>1</tex> — вся обработка пройдёт в цикле первого уровня рекурсии.
 ===Улучшенная быстрая сортировка===

@@ Строка 125: / Строка 125: @@
 <tex>X = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} X_{ij}</tex>, где <tex>X_{ij} = 1</tex> если произошло сравнение <tex>z_i</tex> и <tex>z_j</tex>  и <tex>X_{ij} = 0</tex>, если сравнения не произошло.
-Применим к обоим частям равенства операцию вычисления матожидания и воспользовавшись ее линейностью получим
+Применим к обеим частям равенства операцию вычисления матожидания и воспользовавшись ее линейностью получим
 <tex>E[X] = E\left[\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} X_{ij}\right] = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} E[X_{ij}] = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} Pr\{z_i</tex> сравнивается с <tex>z_j\}</tex>

@@ Строка 154: / Строка 154: @@
              '''continue'''
           '''int''' i = partition(a, l, r)
-          '''if''' (i - 1 > r - i)
+          '''if''' (i - l > r - i)
              s.push(l, i - 1)
              s.push(i + 1, r)

@@ Строка 80: / Строка 80: @@
 ! Шаг 1.0 || Шаг 1.1 || Шаг 1.2 || Шаг 2.0 || Шаг 2.1 || Шаг 2.2 || Шаг 3.0
 |-align="right"
-|style="text-align: center;"|1 2 3 4 <br\> 0 '''0''' 0 0
+|style="text-align: center;"|1 2 3 4 <br> 0 '''0''' 0 0
-| style="text-align: center;"|1 2 3 4 <br\> 0 '''4''' 0 0
+| style="text-align: center;"|1 2 3 4 <br> 0 '''4''' 0 0
-|style="text-align: center;"|1 4 3 2 <br\> 0 0 0 '''4'''
+|style="text-align: center;"|1 4 3 2 <br> 0 0 0 '''4'''
-|style="text-align: center;"|1 4 3 2 <br\> 0 '''0''' 0 4
+|style="text-align: center;"|1 4 3 2 <br> 0 '''0''' 0 4
-|style="text-align: center;"|1 4 3 2 <br\> 0 '''3''' 0 4
+|style="text-align: center;"|1 4 3 2 <br> 0 '''3''' 0 4
-|style="text-align: center;"|1 3 4 2 <br\> 0 0 '''3''' 4
+|style="text-align: center;"|1 3 4 2 <br> 0 0 '''3''' 4
-|style="text-align: center;"|1 3 4 2 <br\> '''0''' 0 3 4
+|style="text-align: center;"|1 3 4 2 <br> '''0''' 0 3 4
 |-
 ! Шаг 3.1 || Шаг 3.2 || Шаг 4.0 || Шаг 4.1 || Шаг 4.2 || colspan="2" style="vertical-align: middle;"| Результат
 |-align="right"
-|style="text-align: center;"|1 3 4 2 <br\> '''2''' 0 3 4
+|style="text-align: center;"|1 3 4 2 <br> '''2''' 0 3 4
-|style="text-align: center;"|3 1 4 2 <br\> 0 '''2''' 3 4
+|style="text-align: center;"|3 1 4 2 <br> 0 '''2''' 3 4
-|style="text-align: center;"|3 1 4 2 <br\> '''0''' 2 3 4
+|style="text-align: center;"|3 1 4 2 <br> '''0''' 2 3 4
-|style="text-align: center;"|3 1 4 2 <br\> '''1''' 2 3 4
+|style="text-align: center;"|3 1 4 2 <br> '''1''' 2 3 4
-|style="text-align: center;"|3 1 4 2 <br\> '''1''' 2 3 4
+|style="text-align: center;"|3 1 4 2 <br> '''1''' 2 3 4
-| colspan="2" style="text-align: center;vertical-align: middle;" |'''1 2 3 4''' <br\> '''2 4 1 3'''
+| colspan="2" style="text-align: center;vertical-align: middle;" |'''1 2 3 4''' <br> '''2 4 1 3'''
 |-

@@ Строка 205: / Строка 205: @@
        '''int''' p = l - 1
        '''int''' q = r
-       '''while''' ''true''
+       '''while''' ''(i <tex> \leqslant </tex> j)''
-          '''while''' (a[i++] < v)
+          '''while''' (a[i] < v)
-          '''while''' (a[j--] > v)
+            i++
-         '''if''' (i == j)
+          '''while''' (a[j] > v)
-            '''break'''
+            j--
           '''if''' (i <tex> \geqslant </tex> j)
              '''break'''
@@ Строка 216: / Строка 216: @@
              p++
              swap(a[p], a[i])
           '''if''' (a[j] == v)
              q--
              swap(a[q], a[j])
        swap(a[i], a[r])
        j = i - 1
        i++
-       '''for''' ('''int''' k = 1; k <tex> \leqslant </tex> p; k++, j--)
+       '''for''' ('''int''' k = l; k <tex> \leqslant </tex> p; k++, j--)
           swap(a[k], a[j])
        '''for''' ('''int''' k = r - 1; k <tex> \geqslant </tex> q; k--, i++)
           swap(a[k], a[i])
-       quicksort(a, 1, j)
+       quicksort(a, l, j)
        quicksort(a, i, r)