В информатике , частичная сортировка является расслабленным вариантом сортировки проблемы. Полная сортировка - это проблема возврата списка элементов таким образом, чтобы все его элементы располагались по порядку, в то время как частичная сортировка возвращает список из k наименьших (или k наибольших) элементов по порядку. Другие элементы (выше k самых маленьких) также могут быть отсортированы, как при частичной сортировке по месту, или могут быть отброшены, что является обычным при потоковой частичной сортировке. Обычным практическим примером частичной сортировки является вычисление «100 лучших» некоторого списка.
С точкой зрения показателей, в частично отсортированном списке, для каждого индекса я от 1 до K, я -й элемент находится в том же самом месте , как это было бы в полной мере отсортированного списка: элемент я из частично отсортированного списка содержит статистические данные заказа i входного списка.
Автономные проблемы
Решение на основе кучи
Кучи допускают простую однопроходную частичную сортировку, когда k фиксировано: вставьте первые k элементов ввода в max-heap. Затем сделайте один проход по оставшимся элементам, добавьте каждый по очереди в кучу и удалите самый большой элемент. Каждая операция вставки занимает O (log k ) времени, в результате чего общее время составляет O ( n log k ) ; этот алгоритм применим при малых значениях k и в сетевых настройках. [1] Другой вариант - создать минимальную кучу для всех значений (сборка занимает O (n) ) и удалить заголовок кучи K раз, каждая операция удаления занимает O (log n ) . В этом случае алгоритм берет O (n + klog n ) .
Решение путем разбиения выделения
Дальнейшее ослабление, требующее только списка из k наименьших элементов, но без требования их упорядочивания, делает проблему эквивалентной выбору на основе разделов ; исходная проблема частичной сортировки может быть решена с помощью такого алгоритма выбора для получения массива, в котором первые k элементов являются k наименьшими, и их сортировки с общей стоимостью O ( n + k log k ) операций. Популярным вариантом реализации этой схемы алгоритма является сочетание быстрого выбора и быстрой сортировки ; результат иногда называют «быстрой сортировкой». [1]
Специализированные алгоритмы сортировки
Более эффективными, чем вышеупомянутые, являются специализированные алгоритмы частичной сортировки, основанные на сортировке слиянием и быстрой сортировке . В варианте быстрой сортировки нет необходимости рекурсивно сортировать разделы, содержащие только элементы, которые попали бы после k -го места в окончательно отсортированный массив (начиная с «левой» границы). Таким образом, если точка опоры попадает в позицию k или более позднюю, мы выполняем рекурсию только на левом разделе: [2]
функция partial_quicksort (A, i, j, k) - если i,>то p ← точка поворота (A, i, j) p ← перегородка (A, i, j, p) partial_quicksort (A, я, p-1, k) если p ,>то partial_quicksort (A, p + 1, j, k)
Результирующий алгоритм называется частичной быстрой сортировкой и требует ожидаемого времени, равного только O ( n + k log k ) , и довольно эффективен на практике, особенно если сортировка выбора используется в качестве базового случая, когда k становится малым относительно n . Тем не менее, временная сложность наихудшего случая все еще очень плохая в случае плохого выбора точки поворота. Поворотный выбор в соответствии с алгоритмом линейного выбора времени для наихудшего случая может использоваться для повышения производительности в наихудшем случае.
Инкрементальная сортировка
Инкрементная сортировка - это «онлайн» версия задачи частичной сортировки, где входные данные выдаются заранее, но k неизвестно: учитывая k- отсортированный массив, должна быть возможность расширить частично отсортированную часть так, чтобы массив стал ( k +1) -сортировано. [3]
Кучи приводят к решению O ( n + k log n ) для частичной онлайн-сортировки: сначала «кучу» за линейное время полного входного массива для создания минимальной кучи. Затем извлеките минимум кучи k раз. [1]
Можно получить другую инкрементную сортировку, изменив quickselect. Версия, разработанная Паредесом и Наварро, поддерживает стек опорных точек между вызовами, так что инкрементная сортировка может быть выполнена путем многократного запроса наименьшего элемента массива A по следующему алгоритму: [3]
Алгоритм IQS ( A : массив, i : целое число, S : стек) возвращает i -й наименьший элемент в A
- Если i = top ( S ) :
- Pop S
- Возврат A [ i ]
- Пусть pivot ← random [ i , top ( S ))
- Обновить сводную страницу ← раздел ( A [ i : top ( S )), A [pivot])
- Наденьте шарнир на S
- Вернуть IQS ( A , i , S )
Стека S инициализируется , чтобы содержать только длина п из A . k -сортировка массива осуществляется вызовом IQS ( A , i , S ) для i = 0, 1, 2, ... ; эта последовательность вызовов имеет сложность в среднем случае O ( n + k log k ) , что асимптотически эквивалентно O ( n + k log n ) . Время наихудшего случая является квадратичным, но это можно исправить, заменив случайный выбор опорной точки алгоритмом медианы медиан . [3]
Поддержка языка / библиотеки
- Стандарт C ++ определяет вызываемую библиотечную функцию
std::partial_sort
. - Python стандартная библиотека включает в себя функции
nlargest
иnsmallest
вheapq
модуле. - Юлия стандартная библиотека включает в себя
PartialQuickSort
реализацию.
Смотрите также
Рекомендации
- ^ a b c Конрадо Мартинес (2004). О частичной сортировке (PDF) . 10-й семинар по анализу алгоритмов.
- ^ Мартинес, Конрадо (2004). Частичная быстрая сортировка (PDF) . Proc. 6-й семинар ACM-SIAM по разработке алгоритмов и экспериментам и 1-й семинар ACM-SIAM по аналитической алгоритмике и комбинаторике.
- ^ а б в Паредес, Родриго; Наварро, Гонсало (2006). «Оптимальная инкрементная сортировка». Proc. Восьмой семинар по разработке алгоритмов и экспериментов (ALENEX) . С. 171–182. CiteSeerX 10.1.1.218.4119 . DOI : 10.1137 / 1.9781611972863.16 . ISBN 978-1-61197-286-3.
Внешние ссылки
- Дж. М. Чемберс (1971). Частичная сортировка . CACM 14 (5): 357–358.