Внутренняя сортировка
Внутренняя сортировка (
периферийным устройствам (соответственно, время доступа значительно меньше). В зависимости от конкретного алгоритма и его реализации данные могут сортироваться в той же области памяти, либо использовать дополнительную оперативную память. Внутренняя сортировка является базовой для любого алгоритма внешней сортировки — отдельные части массива данных сортируются в оперативной памяти и с помощью специального алгоритма сцепляются
в один массив, упорядоченный по ключу.
В современных
системных архитектурах широко применяется подкачка и кэширование памяти. Поэтому в большинстве случаев имеется возможность использовать внутреннюю сортировку даже для задач, в которых объём данных несколько превышает выделяемую процессу оперативную память. Однако, в последнем случае алгоритм сортировки должен хорошо сочетаться с применяемыми операционной системой алгоритмами кэширования и подкачки. В противном случае необходимо использовать подходящий алгоритм внешней сортировки
.
Литература
- Дональд Э. Кнут. Искусство программирования, том 2. Получисленные алгоритмы = The Art of Computer Programming, vol.2. Seminumerical Algorithms, 3-ed. — Вильямс, 2007. — С. 832. — ISBN 978-5-8459-0081-4.
- Роберт Седжвик. Фундаментальные алгоритмы на C. Анализ/Структуры данных/Сортировка/Поиск = Algorithms in C. Fundamentals/Data Structures/Sorting/Searching. — СПб.: ДиаСофтЮП, 2003. — С. 672. — ISBN 5-93772-081-4.
Это заготовка статьи по информатике. Помогите Википедии, дополнив её. |