Частичная сортировка

В информатике — частичная сортировка это упрощенный вариант задачи сортировки . Полная сортировка — это проблема возврата списка элементов так, чтобы все его элементы располагались по порядку, тогда как частичная сортировка возвращает список из k наименьших (или k крупнейших) элементов по порядку. Остальные элементы (после k наименьших элементов) также могут быть отсортированы, как при частичной сортировке на месте, или могут быть отброшены, что часто встречается при потоковой частичной сортировке. Распространенным практическим примером частичной сортировки является вычисление «100 лучших» некоторого списка.

С точки зрения индексов, в частично отсортированном списке для каждого индекса i от 1 до k -й элемент i находится в том же месте, что и в полностью отсортированном списке: элемент i частично отсортированного списка содержит статистику порядка i входного списка.

Оффлайн проблемы

Решение на основе кучи

Кучи допускают простую однопроходную частичную сортировку, когда $k$ фиксировано: вставьте первые $k$ элементов входных данных в максимальную кучу. Затем сделайте один проход по оставшимся элементам, по очереди добавьте каждый в кучу и удалите самый большой элемент. Каждая операция вставки занимает $время O (log k)$ , в результате чего $O (n log k)$ общее время составляет ; этот алгоритм «частичной пирамидальной сортировки» практичен для небольших значений $k$ и в онлайн- настройках. ^[1] Алгоритм «онлайн-выбора кучи», описанный ниже, основанный на минимальной куче, принимает $O (n + k log n)$ . ^[1]

Решение путем выбора раздела

Дальнейшее ослабление, требующее только списка из $k$ наименьших элементов, но не требующее их упорядочения, делает задачу эквивалентной выбору на основе разделов ; исходная проблема частичной сортировки может быть решена с помощью такого алгоритма выбора, чтобы получить массив, в котором первые $k$ элементов являются $k$ наименьшими, и сортировать их с общей стоимостью $O (n + k log k)$ операций. Популярным вариантом реализации этой схемы алгоритма является сочетание быстрого выбора и быстрой сортировки ; результат иногда называют «быстрой сортировкой». ^[1]

В текущих (по состоянию на 2022 год) реализациях STL на C++ обычно выполняется проход пирамидальной выборки для списка из k элементов, за которым следует пирамидальная сортировка для окончательного результата. ^[2]

Специализированные алгоритмы сортировки

Более эффективными, чем вышеупомянутые, являются специализированные алгоритмы частичной сортировки, основанные на сортировке слиянием и быстрой сортировке . В варианте быстрой сортировки нет необходимости рекурсивно сортировать разделы, которые содержат только элементы, которые должны находиться после $k$ -го места в окончательно отсортированном массиве (начиная с «левой» границы). Таким образом, если точка поворота попадает в позицию $k$ или позже, мы выполняем рекурсию только по левому разделу: ^[3]

function partial_quicksort(A, i, j, k) is
    if i < j then
        p ← pivot(A, i, j)
        p ← partition(A, i, j, p)
        partial_quicksort(A, i, p-1, k)
        if p < k-1 then
            partial_quicksort(A, p+1, j, k)

Полученный алгоритм называется частичной быстрой сортировкой и требует ожидаемого времени всего $O (n + k log k)$ и на практике весьма эффективен, особенно если сортировка выбором используется в качестве базового случая, когда $k$ становится малым по сравнению с $n$ . Тем не менее, в случае плохого выбора опорной точки временная сложность в наихудшем случае все равно будет очень плохой. Выбор опорной точки в соответствии с алгоритмом выбора линейного времени для наихудшего случая (см. Быстрая сортировка § Выбор опорной точки ) может использоваться для повышения производительности в наихудшем случае. Частичная быстрая сортировка, быстрый выбор (включая множественный вариант) и быстрая сортировка могут быть обобщены в так называемую сортировку фрагментов . ^[1]

Инкрементная сортировка

Инкрементная сортировка — это версия проблемы частичной сортировки, где входные данные передаются заранее, но $k$ неизвестен: учитывая $k$ -отсортированный массив, должна быть возможность расширить частично отсортированную часть так, чтобы массив стал $(k +1)$ - отсортировано. ^[4]

Кучи приводят к $решению O (n + k log n)$ «онлайн-выбора кучи» для инкрементной частичной сортировки: сначала «кучу» за линейное время, полный входной массив для создания минимальной кучи. Затем извлеките минимум из кучи $k$ раз. ^[1]

Другой инкрементальный вид можно получить, изменив быстрый выбор. Версия, предложенная Паредесом и Наварро, поддерживает стек поворотов между вызовами, так что инкрементную сортировку можно выполнить путем многократного запроса наименьшего элемента массива $A$ из следующего алгоритма: ^[4]

Алгоритм $IQS(A : массив, i : целое число, S : стек)$ возвращает $i$ -й наименьший элемент в $A$

Если я = верх( S ) :
- Поп $С$
- Возврат $А [я]$
Пусть $поворот \leftarrow случайный [i, top(S))$
Обновить $центр \leftarrow раздел(A [i : top(S)), A [центр])$
Нажмите $шарнир$ на $S$
Возврат $IQS(A, i, S)$

Стек $S$ инициализируется так, чтобы содержать только $n$ A $длину$ . $k$ -сортировка массива выполняется вызовом $IQS(A, i, S)$ для $i = 0, 1, 2, ...$ ; эта последовательность вызовов имеет сложность среднего случая $O (n + k log k)$ , что асимптотически эквивалентно $O (n + k log n)$ . Время в худшем случае является квадратичным, но это можно исправить, заменив случайный выбор поворота алгоритмом медианы медиан . ^[4]

Языковая/библиотечная поддержка

Стандарт C++ определяет библиотечную функцию, называемую std::partial_sort.
Стандартная библиотека Python включает функции nlargest и nsmallest в своем heapq модуль.
Стандартная библиотека Julia включает в себя PartialQuickSort алгоритм, используемый в partialsort! и варианты.

См. также

Алгоритм выбора

Ссылки

^ Jump up to: Перейти обратно: ^а ^б ^с ^д ^и Конрадо Мартинес (2004). О частичной сортировке (PDF) . 10-й семинар по анализу алгоритмов.
^ "std::partial_sort" . ru.cppreference.com .
^ Мартинес, Конрадо (2004). Частичная быстрая сортировка (PDF) . Учеб. 6-й семинар ACM-SIAM по алгоритмической разработке и экспериментам и 1-й семинар ACM-SIAM по аналитической алгоритмике и комбинаторике.
^ Jump up to: Перейти обратно: ^а ^б ^с Паредес, Родриго; Наварро, Гонсало (2006). «Оптимальная инкрементная сортировка». Учеб. Восьмой семинар по разработке алгоритмов и экспериментам (ALENEX) . стр. 171–182. CiteSeerX 10.1.1.218.4119 . дои : 10.1137/1.9781611972863.16 . ISBN 978-1-61197-286-3 .

Внешние ссылки

Дж. М. Чемберс (1971). Частичная сортировка . CACM 14 (5): 357–358.

[aofa04slides-1] Jump up to: Перейти обратно: ^а ^б ^с ^д ^и Конрадо Мартинес (2004). О частичной сортировке (PDF) . 10-й семинар по анализу алгоритмов.

[2] "std::partial_sort" . ru.cppreference.com .

[3] Мартинес, Конрадо (2004). Частичная быстрая сортировка (PDF) . Учеб. 6-й семинар ACM-SIAM по алгоритмической разработке и экспериментам и 1-й семинар ACM-SIAM по аналитической алгоритмике и комбинаторике.

[paredes-4] Jump up to: Перейти обратно: ^а ^б ^с Паредес, Родриго; Наварро, Гонсало (2006). «Оптимальная инкрементная сортировка». Учеб. Восьмой семинар по разработке алгоритмов и экспериментам (ALENEX) . стр. 171–182. CiteSeerX 10.1.1.218.4119 . дои : 10.1137/1.9781611972863.16 . ISBN 978-1-61197-286-3 .

[1]

[2]

[3]

[4]