ВУЗ:
Составители:
110
отсортированный массивы располагаются во внешней памяти. В процессе сор-
тировки часть исходного массива считывается в оперативную память, где упо-
рядочивается одним из методов внутренней сортировки, а затем переписывается
во внешнюю память. Этот процесс повторяется несколько раз. Полученные
упорядоченные последовательности записей затем объединяются. Операция
объединения упорядоченных последовательностей данных, размещенных во
внешней
памяти, называется слиянием. Таким образом, внешняя сортировка
включает два этапа обработки: внутреннюю сортировку и слияние.
Разработка способов внешней сортировки является достаточно сложной
самостоятельной задачей, сильно зависящей от состава технических средств и
характеристик вычислительной системы, поэтому ее решением занимается не-
большое число узких специалистов, создающих системное математическое и
программное обеспечение конкретных
вычислительных систем. В составе про-
граммного обеспечения конкретной ЭВМ обычно имеется готовый пакет внеш-
ней сортировки или его можно приобрести. По этой причине методы внешней
сортировки здесь рассматриваться не будут.
Для внутренней сортировки существует множество методов, каждый из
которых имеет свои преимущества и недостатки, а также разную эффективность
для определенных конфигураций
данных и аппаратуры. Критериями оценки
различных методов обычно является среднее число операций сравнения (С),
выполняемых в процессе сортировки, и среднее число перестановок (П) или
обменов элементов. Эффективность сортировки (Э) определяется как частное от
деления среднего числа сравнений на число элементов массива N:
Э = С
ср
/ N
.
При оценке различных методов сортировки достаточно просто опреде-
ляются максимальное и минимальное значения С и П. Средние значения С
ср
и
П
ср
определяются с помощью средств комбинаторного анализа. На практике
ограничиваются аппроксимацией среднего арифметического значений этих ха-
рактеристик.
Обычно операционные системы ЭВМ имеют хотя бы одну программу-
утилиту внутренней сортировки. Однако для конкретной задачи метод, зало-
женный в утилиту, может оказаться малоэффективным и потребуется использо-
вать другой метод. Поэтому важно знать основные
методы внутренней сорти-
ровки для применения их в конкретных задачах.
Методы сортировки линейных структур данных. Процесс сортировки,
проводимый любым методом, состоит из нескольких циклов. В каждом цикле
осуществляется просмотр всей сортируемой последовательности и производят-
ся определенные операции с ее элементами. Один цикл обработки называется
проходом.
Страницы
- « первая
- ‹ предыдущая
- …
- 108
- 109
- 110
- 111
- 112
- …
- следующая ›
- последняя »
