Большой архив статей, книг, документации по программированию, вебдизайну, компьютерной графике, сетям, операционным системам и многому другому
 
<Добавить в Избранное>    <Сделать стартовой>    <Реклама на сайте>    <Контакты>
  Главная Документация Программы Обои   Экспорт RSS E-Books
 
 

   Программирование -> Delphi / Pascal -> Структуры и базы данных, методы сортировки


Метод квадратичной выборки

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


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

Содержание



 

 
Интересное в сети
 
10 новых программ
CodeLobster PHP Edition 3.7.2
WinToFlash 0.7.0008
Free Video to Flash Converter 4.7.24
Total Commander v7.55
aTunes 2.0.1
Process Explorer v12.04
Backup42 v3.0
Predator 2.0.1
FastStone Image Viewer 4.1
Process Lasso 3.70.4
FastStone Image Viewer 4.0
Xion Audio Player 1.0.125
Notepad GNU v.2.2.8.7.7
K-Lite Codec Pack 5.3.0 Full


Наши сервисы
Рассылка новостей. Подпишитесь на рассылку сейчас и вы всегда будете в курсе последних событий в мире информационных технологий.
Новостные информеры. Поставьте наши информеры к себе и у вас на сайте появится дополнительный постоянно обновляемый раздел.
Добавление статей. Если вы являетесь автором статьи или обзора на тему ИТ присылайте материал нам, мы с удовольствием опубликуем его у себя на сайте.
Реклама на сайте. Размещая рекламу у нас, вы получите новых посетителей, которые могут стать вашими клиентами.
 
Это интересно
 

Copyright © CompDoc.Ru
При цитировании и перепечатке ссылка на www.compdoc.ru обязательна. Карта сайта.