AOP_Tom3 (1021738), страница 111

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 111)

В математической терминологии это слово также изобилует значениями (порядок группы, порядок перестановки, порядок точки ветвления, отношение порядка и т. п.). Итак, слово "порядок" приводит к хаосу. В качестве обозначения для процесса упорядочения предлагалось также слово "ранжирование" (эециепс1пя), но оно во многих случаях, по-вндимому, не вполне отражает суть дела, особенно если присутствуют равные элементы, и, кроме того, иногда не согласуется с другнчи терминами. Конечно, слово "сортировка" и само имеет довольно много значений, но оно прочно вошло в программистский жаргон.

Поэтому мы без дальнейших извинений будем использовать слово "сортировка" в узком смысле: "размещение по порядку". Вот некоторые из наиболее важных областей применения сортировки. а) Решение задачи зруппироваиил, когда нужно собрать вместе все элементы с одинаковыми значениями некоторого признака. Допустим, имеется 10 000 элементов. расположенных в случайном порядке, причем значения многих из них равны и нужно переупорядочнть массив так, чтобы элементы с равнымн значениями занимали соседние позиции в массиве.

Это, по существу, тоже задача 'сортировки", но в более широком смысле, и она легко лшжет быть решена путем сортировки массива в указанном выше узком смысле, а именно — в результате расположения элементов в порядке неубывания и1 < из « . и,вввв. Эффект, который может быть достигнут после выполнения этой процедуры, и объясняет изменение первоначального смысла слова "сортировка'. Ь) Поиск общих элементов в двух или более массивах. Если два нли более массивов рассортировать в одном и том же порядке, то можно отыскать в них все общие элементы за один последовательный просмотр всех массивов без возвратов.

Именно этим принципом и воспользовался Перри Мейсон, чтобы раскрыть дело об убийстве (см, эпиграфы к этой главе). Оказывается, сто, как правило, гораздо удобнее просматривать список последовательно, а не перескакивая с места на место случайным образом, если только список не настолько мал, что он целиком помещается в оперативной памяти. Сортировка позволяет использовать последовательный доступ к большим массивам в качестве приемлемой замены прямой адресации.

с) Поиск информации по значениям ключей. Как мы узнаем иэ главы 6, сортировка используется и при поиске; с ее помощью можно сделать результаты обработки данных более удобными для восприятия человеком. В самом деле, подготовленный компьютером список, рассортированный в алфавитном порядке, зачастую выглядит весьма внушительно, даже если содержащиеся в нем числовые данные были рассчятангя неверно. Хотя сортировка традиционно и большей частью использовалась для обработки коммерческих данных, в действительности она является инструментом, полезным в самых разных ситуациях, и поэтому о ней не г юдует забывать.

В упр. 2.3.2 -17 мы обсудили ее примененяе для упрощения алгебраических формул. Упражнения, приведенные ниже, иллюстрирук~т разнообразие типичных применений сортировки. Одной нз первых мощных программных систем, продемонстрировавшнх богатые возможности сортировки, был компилятор ЕАВС Бс1еп11бс Сошрйег, разработанный Дж, Эрдвином (Л. Егдвпш) и Д. Е. Фергюсоном (1У. Е. Гегяпэог1) в фирме Сошрисег Бс1епсеэ Согрога11оп в 1960 году. В этом оптимизирующем компиляторе для расширенного языка ГОВТВА э' сортировка использовалась весьма интенсивно, так что различные алгоритмы компиляции работали с относящимися к ним фрагментами исходного текста программы, расположенными в удобной последова- тельности.

На первом проходе осуществлялся лексический анализ, т. е. выделение в исходной программе лексических единиц (лексем), каждая из которых соответствует либо идентификатору (имени переменной), либо константе, либо оператору и т. д. Каждая лексема получала несколько порядковых номеров. В результате сортировки по именам и соответствующим порядковым номерам все фрагменты текста, в которых использовался данный идентификатор, оказывались собранными вместе. "Определяющие вхождения'; специфицирующие идентификатор как имя функции, простую (параметр) или многомерную (массив) перелзенную, получали меньшие номера, поэтому они оказывались первыми в последовательности лексем, которые соответствовали этому идентификатору.

Тем самым облегчалась проверка правильности употребленяя идентификаторов, распределение памяти с учетом деклараций ЕЦУ17АЕЕМСЕ и т. д. Собранная таким образом информация о каждом идентификаторе присоединялась к соответствующей лексеме. Поэтому не было необходимости хранить в оперативной памяти "таблицу символов" содержащую сведения об идентификаторах.

После такой обработки лексемы снова сортировались по другому порядковому номеру; в результате в программе, по существу, восстанавливался первоначальный порядок, если не считать того, что арифметические выражения оказывались записанными в более удобной 'польской префиксной" форме. Сортировка использовалась и на последующих фазах компиляции — - для упрощения оптимизации циклов, включения в листинг сообщений об ошибках н т. д.

Короче говоря, компилятор был спроектирован так, что всю обработку файлов (а для их хранения использовались весьма распространенные в те времена устройства внешней памяти на магнитных барабанах) можно было выполнять последовательно, Поэтому-то данные и снабжались такими порядковыми номерами, которые позволяли упорядочивать этн данные различными удобными способами. По оценкам произяодителей компьютеров в 60-х годах в среднем более четверти машинно~ и времени тратилось на сортировку. Во многих вычислительных системах нв псе ухо игг больше паловины машинного времени. Исходя из этих статистических данных можно заключить, что либо (1) сортировка имеет много важных применений, либо (й) сю часто пользуются без нужды, либо (ш) применяются в основном неэффективные алгоритмы сортировки.

По-видимому, каждое нз приведенных предположений содержит долю истины. Во всяком гщучае ясно, что сортировка заслуживает серьезного изучения г точки зрения ее практического и~пользования. Но даже если бы сортировка была почти бесполезна, нагплась бы масса других причин заняться ею! Появление изощренных алгоритмов сортировки говорит о том, что она и сама по себе интересна как обьект исследования. В этой области существует множество увлекательных нерешенн1ях задач наряду с весьма немногими уже решенными.

Рассматривая вопрос в более широком плане, мы обнаружим, что алгоритмы сортировки представляют собой интересный частный пример того, как следует гюдходить к решению проблем програмзиирования вообще. Мы познакомилгся со многими важными принципами манипулирования структурами данных и проследим за эволюцией различных методов сортировки, причем читателю часто будет предоставлена возможность самостоятельно 'изобрести велосипед",' как будто бы до него никто с подобными задачами не сталкивался.

Обобщение этих частных методов позволит нам в значительной степени овладеть теми подходами, которые помогут создавать качественные алгоритмы для решения других проблем, связанных с использованием компьютеров. Методы сортировки служат великолепной иллюстрацией базовых концепций аиа.щиа алеоришмов, т. е. оценки качества алгоритмов, что, в свою очередь, позволяет разумно делать выбор среди, казалось бы, равноценных методов. Читатели, имеющие склонность к математике, найдут в этой главе немало поучительных способов оценки скорости работы алгоритмов и методов решения сложных рекуррентных соотношений.

С другой стороны, изложение построено так, что читатели, не имеющие такой склонности, могут безболезненно пропускать выкладки. Прежде чем двигаться далыпе, необходимо более четко сформулировать задачу и ввести соответствующую терминологию. Пусть надо упорядочить Х элементов ЕЕы ЕЕа,, Ля. Назовем их записями, а всю совокупность Х записей назовем файлом. Каждая запись ЕЕэ имеет ключ, К, который и управляет процессом сортировки.

Помимо ключа, запись может содержать дополнительную 'сопутствующую информацию", которая не влияет на сортировку, но всегда остается в этой записи. Отношение порядка "<ь на множестве ключей вводится таким образом, чтобы для любых трех значений ключей а, Ь, с выполнялись следующие условия: 1) справедливо одно и только одно из соотношений а < Ь, а = Ь, Ь < а (закон трихотомии); й) если а < Ь и Ь < с, то а < с (закон транзитивности). Эти два свойства определяют математическое понятие линейного упорядочения, называемого также совер|иеннмм упорядочением. Любое множество с отношением "<'~ удовлетворяющим обоим этим свойствам, поддается сортировке большинством методов., описанных в этой главе, хотя некоторые из методов годятся только для числовых и буквенных ключей с общепринятым отношением порядка.

Задача сортировки — найти такую перестановку записей р(1) р(2)...р(11') с индексами (1, 2,..., Х), после которой ключи расположились бы в порядке неубывания: КгН1 < К,р~ < " < К,~мр (1) Сортировка называется устойчивой, если она удовлетворяет такому дополнительному условию, что записи с одинаковыми ключами остаются в прежнем порядке, т, е., другими словами, (2) р(1) < р(Е) для любых К,1О = К„О1 и 1 < 1'. В одних случаях придется физически перемещать записи в памяти так, чтобы их ключи были упорядочены; в других случаях достаточно создать вспомогательную таблицу, которая некоторым образом описывает перестановку и обеспечивает доступ к записям в соответствия с порядком их ключей.

Характеристики

Список файлов книги