Изменения
Новая страница: «{{В разработке}} {{Определение |definition= '''<tex>k</tex>-ой порядковой статистикой''' набора элементо…»
{{В разработке}}
{{Определение
|definition=
'''<tex>k</tex>-ой порядковой статистикой''' набора элементов линейно упорядоченного множества называется такой его элемент, который является <tex>k</tex>-ым элементом набора в порядке сортировки
}}
== Модификация QuickSort ==
=== Описание алгоритма ===
Будем использовать процедуру рассечения массива элементов из алгоритма сортировки QuickSort. Пусть нам надо найти <tex>k</tex>-ую порядковую статистику, а после рассечения опорный элемент встал на позицию <tex>m</tex>. Возможно три случая:
* '''k = m'''. Порядковая статистика найдена.
* '''k < m'''. Рекурсивно ищем <tex>k</tex>-ую статистику в первой половине массива.
* '''k > m'''. Рекурсивно ищем <tex>(k - m - 1)</tex>-ую статистику во второй половине массива.
=== Код алгоритма ===
Ниже представлен код представленного алгоритма. При реализации, однако, вместо рекурсивных вызовов изменяются границы поиска статистики во внешнем цикле. В коде счититаем, что процедура '''partition''' принимает массив и границы отрезка, который будет рассечён (причём правая граница отрезка не включается) и возвращает индекс опорного элемента. Также, считается, что массив индексируется с нуля.
int findOrderStatistic(int[] array, int k) {
int left = 0, right = array.length;
while (true) {
int mid = partition(array, left, right);
if (mid == k) {
return array[mid];
}
else if (k < mid) {
right = mid;
}
else {
k -= mid + 1;
left = mid + 1;
}
}
}
=== Анализ времени работы ===
Аналогично QuickSort, может возникнуть такой же худщий случай (процедура '''partition''' возвращает каждый раз левую или правую границу рассматриваемой части), при котором время работы составит <tex>\Omega(n^2)</tex>. Однако, если считать, что '''partition''' возвращает все элементы рассматриваемого отрезка с равной вероятностью, то можно оценить матожидание времени работы как <tex>O(n)</tex>.
{{Определение
|definition=
'''<tex>k</tex>-ой порядковой статистикой''' набора элементов линейно упорядоченного множества называется такой его элемент, который является <tex>k</tex>-ым элементом набора в порядке сортировки
}}
== Модификация QuickSort ==
=== Описание алгоритма ===
Будем использовать процедуру рассечения массива элементов из алгоритма сортировки QuickSort. Пусть нам надо найти <tex>k</tex>-ую порядковую статистику, а после рассечения опорный элемент встал на позицию <tex>m</tex>. Возможно три случая:
* '''k = m'''. Порядковая статистика найдена.
* '''k < m'''. Рекурсивно ищем <tex>k</tex>-ую статистику в первой половине массива.
* '''k > m'''. Рекурсивно ищем <tex>(k - m - 1)</tex>-ую статистику во второй половине массива.
=== Код алгоритма ===
Ниже представлен код представленного алгоритма. При реализации, однако, вместо рекурсивных вызовов изменяются границы поиска статистики во внешнем цикле. В коде счититаем, что процедура '''partition''' принимает массив и границы отрезка, который будет рассечён (причём правая граница отрезка не включается) и возвращает индекс опорного элемента. Также, считается, что массив индексируется с нуля.
int findOrderStatistic(int[] array, int k) {
int left = 0, right = array.length;
while (true) {
int mid = partition(array, left, right);
if (mid == k) {
return array[mid];
}
else if (k < mid) {
right = mid;
}
else {
k -= mid + 1;
left = mid + 1;
}
}
}
=== Анализ времени работы ===
Аналогично QuickSort, может возникнуть такой же худщий случай (процедура '''partition''' возвращает каждый раз левую или правую границу рассматриваемой части), при котором время работы составит <tex>\Omega(n^2)</tex>. Однако, если считать, что '''partition''' возвращает все элементы рассматриваемого отрезка с равной вероятностью, то можно оценить матожидание времени работы как <tex>O(n)</tex>.
