Cтраница 2
Доля стекла в отходах не будет значительно возрастать в последующие 30 лет. Наличие стекла осложняет работу оператора печи для сжигания. Если проблема сортировки стекла не будет решена, то надо идти по пути разработки очень дешевых пластмассовых упаковок для напитков и продуктов, особенно био-разлагающихся. [16]
Многие из возможных приложений сортировки часто отдают предпочтение простейшим алгоритмам. Во-первых, очень часто программа сортировки используется всего лишь один или небольшое число раз. После того как удалось решить проблему сортировки для некоторого набора данных, в дальнейшем потребность в программе сортировки в приложениях, которые манипулируют этими данными, отпадает. Если элементарная сортировка работает не медленней других частей приложения, осуществляющего обработку данных - например, считывание данных или их вывод на печать - то отпадает необходимость в поиске более быстрых методов сортировки. Если число сортируемых элементов не очень большое ( скажем, не превышает нескольких сотен элементов), можно просто воспользоваться простым методом и не ломать голову над тем, как работает интерфейс для системной сортировки, или как написать и отладить программу, реализующую какой-нибудь сложный метод сортировки. Во-вторых, элементарные методы всегда годятся для файлов небольших размеров ( состоящих из нескольких десятков элементов) - сложные алгоритмы в общем случае обусловливают непроизводительные затраты ресурсов, а это приводит к тому, что на файлах небольших размеров они работают медленнее элементарных методов сортировки. Эта проблема не попадет в фокус нашего внимания до тех пор, пока не возникнет необходимость сортировки большого числа файлов небольших размеров, однако следует иметь в виду, что приложения с подобного рода требованиями встречаются достаточно часто. Другими типами файлов, сортировка которых существенно упрощена, являются файлы, с почти ( или уже) завершенной сортировкой или файлы, которые содержат большое число дублированных ключей. Далее можно будет убедиться в том, что некоторые методы из числа простейших особенно эффективны при сортировке хорошо структурированных файлов. [17]
Язык АПЛ, напоминающий своей компактностью и возможностями современные математические теории, зародился, пожалуй, раньше, чем телетайпная алгебра Фортрана и Алгола. АПЛ был задуман им не как язык программирования. При подготовке своей диссертации по машинному решению линейных дифференциальных уравнений для экономико-математических моделей типа затраты-вы-пуск [3] автор столкнулся с алгоритмом, связанным с проблемами сортировки, который плохо поддавался описанию, в результате чего появилась необходимость изобрести оригинальную нотацию. Первоначально его творение было известно в Гарварде как нотация Айверсона. [18]
Это привело к развитию вычислительных методов, применимых к широкому кругу комбинаторных задач; некоторые из этих методов мы обсудим в этой главе. Наиболее фундаментальным и часто используемым является алгоритм перебора с возвратом ( разд. Теория графов относится к областям комбинаторной математики, имеющим самые широкие приложения; в разд. Раздел 2.5 содержит введение в проблему сортировки, которая непосвященным часто кажется тривиальной, а в действительности связана с глубокими математическими исследованиями и чрезвычайно важна практически. Если бы удалось выяснить, чем заняты в произвольно заданный момент времени все ЭВМ мира, то обнаружилось бы, что большая их часть занимается именно сортировкой. [19]
Как сделать так, чтобы несколько независимых процессоров работали совместно, решая одну задачу сортировки. Управляют ли процессоры внешними запоминающими устройствами или сами являются самостоятельными вычислительными системами - от этого во многом зависит алгоритм функционирования высокопроизводительных вычислительных систем. Проблема параллельных вычислений в последнее время широко изучается. Разработано множество типов вычислительных машин параллельного действия, предложены разнообразные модели параллельных вычислений. Во всех этих случаях проблема сортировки выступает как эффективное средство тестирования и того, и другого. [20]
Прежде чем переходить к рассмотрению конкретных алгоритмов, полезно обсудить общую терминологию и базовые принципы построения алгоритмов сортировки. Эти понятия являются естественными абстракциями для современных сред программирования. Ключи, которые - суть лишь часть ( зачастую очень небольшая часть) элементов, используются для управления сортировкой. Специфические характеристики ключей и элементов в разных приложениях могут существенно отличаться друг от друга, однако абстрактное понятие размещения ключей и связанной с ними информации в определенном порядке и представляет собой суть проблемы сортировки. [21]