Метод квадратичной выборки
Данный метод по сравнению с
сортировкой выборкой уменьшает число сравнений,но
требует дополнительного объема памяти.
Сортируемая таблица, состоящая из n элементов,
разделяется на n групп по sqrt(n) элементов в каждой.
Если n не является точным квадратом,то таблица
разделяется на n' групп, где n'
есть ближайший точный квадрат, больший n. В
каждой группе выбирается наименьший элемент,
который пересылается во вспомогательный список.
Вспомогательный список просматривается, и
наименьший его элемент пересылается в зону
вывода (в зоне вывода формируется
отсортированный список). Далее из группы,
содержащей элемент, посылаемый в зону вывода,
выбирается новый наименьший элемент, который
помещается во вспомогательный список. Затем
другой просмотр вспомогательного списка
выбырает новый наименьший элемент, который
является вторым по величине во всем списке. Он
пересылается в зону вывода. Элементы групп,
которые уже посланы во вспомогательный список,
заменяются большими фиктивными величинами.
Таким образом, при сортировке квадратичной
выборкой попеременно просматриваются то
вспоиогательный список, то группа, до тех пор,
пока все группы не будут исчерпаны. Такое
состояние наступает, когда все группы посылают
во вспомогательный список фиктивные величины.
Модификацией данного метода является
квадратичная выборка с предварительной
сортировкой. В этом методе группы сначала
полностью упорядочиваются, а затем уже
выполняются сравнения между группами.
Общее число сравнений для случая точного
квадрата равно приблизительно 2n*sqrt(n),
необходимый резерв памяти - поле длиной (n+sqrt(n))
элемент.
Содержание
|
