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

Ctrlalt в 02:35, 11 ноября 2022

2022-11-11T02:35:42Z

← Предыдущая версия		Версия от 02:35, 11 ноября 2022
Строка 19:		Строка 19:
	int i = l + 1, j = r;		int i = l + 1, j = r;
	while (1) {		while (1) {
	while (i <= r && a[i] < a[l])		while (i <= j && a[i] < a[l])
	i++;		i++;
	while (j ~~> l~~ && a[j] > a[l])		while (i <= j && a[j] > a[l])
	j--;		j--;
	if (i >= j)		if (i > j)
	break;		break;
	swap(a[i++], a[j--]);		swap(a[i++], a[j--]);

Ctrlalt в 10:24, 9 ноября 2021

2021-11-09T10:24:32Z

← Предыдущая версия		Версия от 10:24, 9 ноября 2021
Строка 8:		Строка 8:
	Если в качестве опорного выбирать любой фиксированный элемент, всегда можно составить контртест, на котором время работы будет квадратичным. Чтобы избежать худшего случая, требуется в качестве опорного выбирать случайный элемент в рассматриваемом диапазоне. Можно показать, что ожидаемая сложность при этом составит O(NlogN); константа у быстрой сортировки, как правило, меньше, чем у других сортировок с подобной асимптотической сложностью.		Если в качестве опорного выбирать любой фиксированный элемент, всегда можно составить контртест, на котором время работы будет квадратичным. Чтобы избежать худшего случая, требуется в качестве опорного выбирать случайный элемент в рассматриваемом диапазоне. Можно показать, что ожидаемая сложность при этом составит O(NlogN); константа у быстрой сортировки, как правило, меньше, чем у других сортировок с подобной асимптотической сложностью.

			minstd_rand generator;

	void quickSort(vector<int> &a, int l, int r) {		void quickSort(vector<int> &a, int l, int r) {
	if (l >= r)		if (l >= r)
Строка 34:		Строка 36:

	minstd_rand generator;		minstd_rand generator;

	{{Changed\|int}} quickSort(vector<int> &a, int l, int r, {{Changed\|1=int k}}) {		{{Changed\|int}} quickSort(vector<int> &a, int l, int r, {{Changed\|1=int k}}) {
	uniform_int_distribution<int> distribution(l, r);		uniform_int_distribution<int> distribution(l, r);

Ctrlalt: /* Ссылки */

2021-11-09T10:22:28Z

Ссылки

← Предыдущая версия		Версия от 10:22, 9 ноября 2021
Строка 61:		Строка 61:
	== Ссылки ==		== Ссылки ==
	Теория:		Теория:
	* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%91%D1%8B%D1%81%D1%82%D1%80%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0 neerc.ifmo.ru/wiki ~~—~~ Быстрая сортировка]		* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%91%D1%8B%D1%81%D1%82%D1%80%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0 neerc.ifmo.ru/wiki — Быстрая сортировка]
	* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_k-%D0%BE%D0%B9_%D0%BF%D0%BE%D1%80%D1%8F%D0%B4%D0%BA%D0%BE%D0%B2%D0%BE%D0%B9_%D1%81%D1%82%D0%B0%D1%82%D0%B8%D1%81%D1%82%D0%B8%D0%BA%D0%B8 neerc.ifmo.ru/wiki ~~—~~ Поиск k-ой порядковой статистики]		* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_k-%D0%BE%D0%B9_%D0%BF%D0%BE%D1%80%D1%8F%D0%B4%D0%BA%D0%BE%D0%B2%D0%BE%D0%B9_%D1%81%D1%82%D0%B0%D1%82%D0%B8%D1%81%D1%82%D0%B8%D0%BA%D0%B8 neerc.ifmo.ru/wiki — Поиск k-ой порядковой статистики]
	* [~~http://brestprog.neocities.org/lections/sort.html brestprog.neocities.org — Сортировка]~~		* [https://algorithmica.org/ru/sorting algorithmica.org — Сортировки]
	* [http://algorithmica.org/tg/~~quicksort~~ algorithmica.org — ~~Быстрая сортировка (см. последнюю часть конспекта)~~]		* [https://algs4.cs.princeton.edu/lectures/keynote/23Quicksort.pdf algs4.cs.princeton.edu/lectures — 2.3 Quicksort]
	* [~~http~~://algs4.cs.princeton.edu/lectures/23Quicksort.pdf algs4.cs.princeton.edu/lectures ~~—~~ 2.3 Quicksort]
	* [http://brilliant.org/wiki/quick-sort/ Brilliant.org — Quicksort]		* [http://brilliant.org/wiki/quick-sort/ Brilliant.org — Quicksort]
	Демонстрация:		Демонстрация:
	* [http://www.sorting-algorithms.com/quick-sort Sorting Algorithm Animations ~~—~~ Quick Sort]		* [http://www.sorting-algorithms.com/quick-sort Sorting Algorithm Animations — Quick Sort]
	* [http://visualgo.net/sorting.html VisuAlgo ~~—~~ Sorting]		* [http://visualgo.net/sorting.html VisuAlgo — Sorting]
	Код:		Код:
	* [~~http~~://github.com/indy256/codelibrary/blob/master/java/~~src~~/~~Sort~~.java ~~CodeLibrary — Sorting algorithms~~]		* [https://github.com/indy256/codelibrary/blob/master/java/sort/Quicksort.java indy256/codelibrary/java/sort/Quicksort.java]
	* [~~http~~://github.com/indy256/codelibrary/blob/master/java/~~src~~/NthElement.java ~~CodeLibrary — Kth order statistic in O(N) on average~~]		* [https://github.com/indy256/codelibrary/blob/master/java/sort/NthElement.java indy256/codelibraryjava/sort/NthElement.java]
	* [~~http~~://github.com/ADJA/algos/blob/master/Other/QuickSort.cpp ~~Algos — Quick sort with random pivot element~~]		* [https://github.com/ADJA/algos/blob/master/Other/QuickSort.cpp ADJA/algos/Other/QuickSort.cpp]
	* algs4.cs.princeton.edu/code ~~—~~ [http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/Quick.java.html quicksort], [http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/Quick3way.java.html quicksort with 3-way partitioning], [http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/QuickX.java.html optimized quicksort]		* algs4.cs.princeton.edu/code — [http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/Quick.java.html quicksort], [http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/Quick3way.java.html quicksort with 3-way partitioning], [http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/QuickX.java.html optimized quicksort]
	Задачи:		Задачи:
	* [http://informatics.mccme.ru/course/view.php?id=3 informatics.mccme.ru — Курс «Поиск и сортировка» — часть 4]		* [http://informatics.mccme.ru/course/view.php?id=3 informatics.mccme.ru — Курс «Поиск и сортировка» — часть 4]

Ctrlalt в 10:10, 9 ноября 2021

2021-11-09T10:10:14Z

← Предыдущая версия		Версия от 10:10, 9 ноября 2021
Строка 1:		Строка 1:
			== Алгоритм ==
			Выбираем в массиве опорный элемент. За Θ(N) делим массив на части: (<= опорного), (опорный), (>= опорного). Левую и правую части сортируем рекурсивно.

			В лучшем случае, если опорный элемент будет делить массив примерно пополам, получим сложность O(NlogN), как у сортировки слиянием.

			С другой стороны, если опорный элемент каждый раз выбирать неудачно (близко к минимуму или максимуму), то одна из половин будет почти пустой, а сложность деградирует до O(N<sup>2</sup>).

			Если в качестве опорного выбирать любой фиксированный элемент, всегда можно составить контртест, на котором время работы будет квадратичным. Чтобы избежать худшего случая, требуется в качестве опорного выбирать случайный элемент в рассматриваемом диапазоне. Можно показать, что ожидаемая сложность при этом составит O(NlogN); константа у быстрой сортировки, как правило, меньше, чем у других сортировок с подобной асимптотической сложностью.

			void quickSort(vector<int> &a, int l, int r) {
			if (l >= r)
			return;

			uniform_int_distribution<int> distribution(l, r);
			swap(a[l], a[distribution(generator)]);

			int i = l + 1, j = r;
			while (1) {
			while (i <= r && a[i] < a[l])
			i++;
			while (j > l && a[j] > a[l])
			j--;
			if (i >= j)
			break;
			swap(a[i++], a[j--]);
			}
			swap(a[l], a[j]);

			quickSort(a, l, j - 1);
			quickSort(a, j + 1, r);
			}

			== K-я порядковая статистика за O(N) ==

			minstd_rand generator;

			{{Changed\|int}} quickSort(vector<int> &a, int l, int r, {{Changed\|1=int k}}) {
			uniform_int_distribution<int> distribution(l, r);
			swap(a[l], a[distribution(generator)]);

			int i = l + 1, j = r;
			while (1) {
			while (i <= r && a[i] < a[l])
			i++;
			while (j > l && a[j] > a[l])
			j--;
			if (i >= j)
			break;
			swap(a[i++], a[j--]);
			}
			swap(a[l], a[j]);

			{{Changed\|1=if (k < j)}}
			{{Changed\|1=return quickSort(a, l, j - 1, k);}}
			{{Changed\|1=if (k == j)}}
			{{Changed\|1=return a[j];}}
			{{Changed\|1=else}}
			{{Changed\|1=return quickSort(a, j + 1, r, k);}}
			}

	== Ссылки ==		== Ссылки ==
	Теория:		Теория:

Ctrlalt: /* Ссылки */

2020-01-02T17:36:02Z

Ссылки

← Предыдущая версия		Версия от 17:36, 2 января 2020
Строка 6:		Строка 6:
	* [http://algorithmica.org/tg/quicksort algorithmica.org — Быстрая сортировка (см. последнюю часть конспекта)]		* [http://algorithmica.org/tg/quicksort algorithmica.org — Быстрая сортировка (см. последнюю часть конспекта)]
	* [http://algs4.cs.princeton.edu/lectures/23Quicksort.pdf algs4.cs.princeton.edu/lectures — 2.3 Quicksort]		* [http://algs4.cs.princeton.edu/lectures/23Quicksort.pdf algs4.cs.princeton.edu/lectures — 2.3 Quicksort]
			* [http://brilliant.org/wiki/quick-sort/ Brilliant.org — Quicksort]
	Демонстрация:		Демонстрация:
	* [http://www.sorting-algorithms.com/quick-sort Sorting Algorithm Animations — Quick Sort]		* [http://www.sorting-algorithms.com/quick-sort Sorting Algorithm Animations — Quick Sort]

Ctrlalt: /* Ссылки */

2019-08-30T13:55:44Z

Ссылки

← Предыдущая версия		Версия от 13:55, 30 августа 2019
Строка 4:		Строка 4:
	* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_k-%D0%BE%D0%B9_%D0%BF%D0%BE%D1%80%D1%8F%D0%B4%D0%BA%D0%BE%D0%B2%D0%BE%D0%B9_%D1%81%D1%82%D0%B0%D1%82%D0%B8%D1%81%D1%82%D0%B8%D0%BA%D0%B8 neerc.ifmo.ru/wiki — Поиск k-ой порядковой статистики]		* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_k-%D0%BE%D0%B9_%D0%BF%D0%BE%D1%80%D1%8F%D0%B4%D0%BA%D0%BE%D0%B2%D0%BE%D0%B9_%D1%81%D1%82%D0%B0%D1%82%D0%B8%D1%81%D1%82%D0%B8%D0%BA%D0%B8 neerc.ifmo.ru/wiki — Поиск k-ой порядковой статистики]
	* [http://brestprog.neocities.org/lections/sort.html brestprog.neocities.org — Сортировка]		* [http://brestprog.neocities.org/lections/sort.html brestprog.neocities.org — Сортировка]
			* [http://algorithmica.org/tg/quicksort algorithmica.org — Быстрая сортировка (см. последнюю часть конспекта)]
	* [http://algs4.cs.princeton.edu/lectures/23Quicksort.pdf algs4.cs.princeton.edu/lectures — 2.3 Quicksort]		* [http://algs4.cs.princeton.edu/lectures/23Quicksort.pdf algs4.cs.princeton.edu/lectures — 2.3 Quicksort]
	Демонстрация:		Демонстрация:

Ctrlalt в 20:25, 24 июля 2016

2016-07-24T20:25:08Z

← Предыдущая версия		Версия от 20:25, 24 июля 2016
Строка 12:		Строка 12:
	* [http://github.com/indy256/codelibrary/blob/master/java/src/NthElement.java CodeLibrary — Kth order statistic in O(N) on average]		* [http://github.com/indy256/codelibrary/blob/master/java/src/NthElement.java CodeLibrary — Kth order statistic in O(N) on average]
	* [http://github.com/ADJA/algos/blob/master/Other/QuickSort.cpp Algos — Quick sort with random pivot element]		* [http://github.com/ADJA/algos/blob/master/Other/QuickSort.cpp Algos — Quick sort with random pivot element]
	* algs4.cs.princeton.edu/code — [http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/Quick.java quicksort], [http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/Quick3way.java quicksort with 3-way partitioning], [http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/QuickX.java optimized quicksort]		* algs4.cs.princeton.edu/code — [http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/Quick.java.html quicksort], [http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/Quick3way.java.html quicksort with 3-way partitioning], [http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/QuickX.java.html optimized quicksort]
	Задачи:		Задачи:
	* [http://informatics.mccme.ru/course/view.php?id=3 informatics.mccme.ru — Курс «Поиск и сортировка» — часть 4]		* [http://informatics.mccme.ru/course/view.php?id=3 informatics.mccme.ru — Курс «Поиск и сортировка» — часть 4]

Ctrlalt в 20:23, 24 июля 2016

2016-07-24T20:23:35Z

← Предыдущая версия		Версия от 20:23, 24 июля 2016
Строка 12:		Строка 12:
	* [http://github.com/indy256/codelibrary/blob/master/java/src/NthElement.java CodeLibrary — Kth order statistic in O(N) on average]		* [http://github.com/indy256/codelibrary/blob/master/java/src/NthElement.java CodeLibrary — Kth order statistic in O(N) on average]
	* [http://github.com/ADJA/algos/blob/master/Other/QuickSort.cpp Algos — Quick sort with random pivot element]		* [http://github.com/ADJA/algos/blob/master/Other/QuickSort.cpp Algos — Quick sort with random pivot element]
			* algs4.cs.princeton.edu/code — [http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/Quick.java quicksort], [http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/Quick3way.java quicksort with 3-way partitioning], [http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/QuickX.java optimized quicksort]
	Задачи:		Задачи:
	* [http://informatics.mccme.ru/course/view.php?id=3 informatics.mccme.ru — Курс «Поиск и сортировка» — часть 4]		* [http://informatics.mccme.ru/course/view.php?id=3 informatics.mccme.ru — Курс «Поиск и сортировка» — часть 4]

Ctrlalt в 19:43, 27 января 2016

2016-01-27T19:43:17Z

← Предыдущая версия		Версия от 19:43, 27 января 2016
Строка 3:		Строка 3:
	* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%91%D1%8B%D1%81%D1%82%D1%80%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0 neerc.ifmo.ru/wiki — Быстрая сортировка]		* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%91%D1%8B%D1%81%D1%82%D1%80%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0 neerc.ifmo.ru/wiki — Быстрая сортировка]
	* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_k-%D0%BE%D0%B9_%D0%BF%D0%BE%D1%80%D1%8F%D0%B4%D0%BA%D0%BE%D0%B2%D0%BE%D0%B9_%D1%81%D1%82%D0%B0%D1%82%D0%B8%D1%81%D1%82%D0%B8%D0%BA%D0%B8 neerc.ifmo.ru/wiki — Поиск k-ой порядковой статистики]		* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_k-%D0%BE%D0%B9_%D0%BF%D0%BE%D1%80%D1%8F%D0%B4%D0%BA%D0%BE%D0%B2%D0%BE%D0%B9_%D1%81%D1%82%D0%B0%D1%82%D0%B8%D1%81%D1%82%D0%B8%D0%BA%D0%B8 neerc.ifmo.ru/wiki — Поиск k-ой порядковой статистики]
			* [http://brestprog.neocities.org/lections/sort.html brestprog.neocities.org — Сортировка]
	* [http://algs4.cs.princeton.edu/lectures/23Quicksort.pdf algs4.cs.princeton.edu/lectures — 2.3 Quicksort]		* [http://algs4.cs.princeton.edu/lectures/23Quicksort.pdf algs4.cs.princeton.edu/lectures — 2.3 Quicksort]
	Демонстрация:		Демонстрация:

Ctrlalt: /* Ссылки */

2015-07-16T04:55:29Z

Ссылки

← Предыдущая версия		Версия от 04:55, 16 июля 2015
Строка 2:		Строка 2:
	Теория:		Теория:
	* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%91%D1%8B%D1%81%D1%82%D1%80%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0 neerc.ifmo.ru/wiki — Быстрая сортировка]		* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%91%D1%8B%D1%81%D1%82%D1%80%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0 neerc.ifmo.ru/wiki — Быстрая сортировка]
			* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_k-%D0%BE%D0%B9_%D0%BF%D0%BE%D1%80%D1%8F%D0%B4%D0%BA%D0%BE%D0%B2%D0%BE%D0%B9_%D1%81%D1%82%D0%B0%D1%82%D0%B8%D1%81%D1%82%D0%B8%D0%BA%D0%B8 neerc.ifmo.ru/wiki — Поиск k-ой порядковой статистики]
	* [http://algs4.cs.princeton.edu/lectures/23Quicksort.pdf algs4.cs.princeton.edu/lectures — 2.3 Quicksort]		* [http://algs4.cs.princeton.edu/lectures/23Quicksort.pdf algs4.cs.princeton.edu/lectures — 2.3 Quicksort]
	Демонстрация:		Демонстрация: