Вид - сортировка
Cтраница 2
Мы переходим к рассмотрению другого аспекта задачи абстрактной сортировки, которая возникает, когда сортируемый файл настолько велик, что не помещается целиком в оперативной памяти Компьютера. Существует множество различных типов устройств внешней сортировки, которые накладывают различные ограничения на атомарные операции, применяемые при реализации таких видов сортировки. Кроме того, будет полезно изучить методы сортировки, использующие две простейшие базовые операции: операция считывания ( read) данных из внешнего запоминающего устройства в оперативную память и операция записи ( write) данных из оперативной памяти на внешнее запоминающее устройство. Мы полагаем, что стоимость этих двух операции настолько выше стоимости простейших примитивных вычислительных операций, что последние в дальнейшем мы можем полностью игнорировать. [16]
 |
Чтобы разместить заголовок таблицы, необходимо объединить все ячейки в верхней строке таблицы. [17] |
Сортировка очень удобна во многих случаях. Можно отсортировать таблицу имен, разместить их в алфавитном порядке, затем скопировать таблицу и сортировать все снова по номеру в платежной ведомости служащих, эли, допустим, у вас есть таблица, в которой указаны объемы продаж вашей компании, отсортированные по регионам, но позже отдел маркетинга принял решение, что данные будут лучше выглядеть, если их сортировать по товарам. Этот вид сортировки выполняется довольно просто. [18]
Сортировка способом распределения предусматривает разделение сортируемых записей на группы, характеризуемые одинаковым значением сортируемого признака. Например, так сортируются пачки перфокарт по какой-либо колонке. При таком, виде сортировки записи с одинаковым значением сортируемого признака собираются в одну группу, причем порядок расположения записей внутри группы не имеет значения. [19]
Восходящая сортировка слиянием ( слева) состоит из последовательности проходов по файлу, которые выполняют слияние отсортированных подфайлов до тех пор, пока не останется только один подфайл. Каждый элемент файла, за исключением разве что нескольких в самом конце, используется в каждом проходе. В противоположность этому, нисходящая сортировка слиянием ( справа) сортирует первую половину файла, прежде чем перейти ко второй половине ( в рекурсивном режиме), так что схемы выполнения обеих видов сортировки слиянием существенно различаются. [20]
Методы сортировки являются критическими компонентами многих прикладных систем. Довольно часто предпринимаются специальные меры, чтобы сделать сортировку максимально быстрой или придать ей способность выполнять обработку особо крупных файлов. Нередки случаи, когда специально для того, чтобы повысить возможности сортировки, в вычислительные системы вносятся усовершенствования, повышающие ее производительность, разрабатываются специальные аппаратные средства или просто выбираются компьютерные системы, в основу которых положены новые архитектурные решения. Во всех подобных случаях представления об относительной стоимости операций, выполняемых над сортируемыми данными, которыми мы руководствуемся, могут оказаться непригодными. В данной главе мы исследуем примеры методов сортировки, которые разрабатываются для эффективного применения на конкретных типах машин. Мы рассмотрим некоторые примеры ограничений, налагаемых на высокопроизводительные аппаратные средства, а также несколько методов, которые могут оказаться полезными на практике в плане реализации высокоэффективных видов сортировки. [21]
Страницы: 1 2