Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 4

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

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

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

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

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

В упр. 2.3.2-17 мы обсудили ее применение для упрощения алгебраических формул. Упражнения, приведенные ниже, иллюстрируют разнообразие типичных применений сортировки. Одной нз первых мощных программных систем, продемонстрировавших богатые возможности сортировки, был компилятор ЕАКС Зс)епг1бс Сошр!1ег, разработанный Дж. Эрдвином (Л. Егди1пп) и Д. Е. сйергюсоном (В.

Е. Еегкпзоп) в фирме Соспрцгег Яс1епсеэ Согрогаг1оп в 1960 году. В этом оптимизирующем компиляторе для расширенного языка ЕО)П'ВА к сортировка испольювалась весьма интенсивно, так что различные алгоритмы компиляции работали с относящимися к ним фрагментами исходного текста программы, расположенными в удобной последова- тельности. На первом проходе осуществлялся лексический анализ, т. е. выделение в исходной программе лексических единиц (лексем), каждая из которых соответствует либо идентификатору (имени переменной), либо константе, либо оператору н т. д.

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

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

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

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

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

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

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

Отношение порядка "<" на множестве ключей вводится таким образом, чтобы для любых трех значений ключей а, Ь, с выполнялись следующие условия: !) справедливо одно и только одно из соотношений а < Ь, а = Ь, Ь < а (закон трихотомии); И) если а < Ь и Ь < с, то а < с (закон транзитнвностн).

Эти два свойства определяют математическое понятие линейного упора!»оченил, называемого также совершенным 1»норлдочением. Любое множество с отношением "<", удовлетворяющим обоим этим свойствам, поддается сортировке болыпинствоь! методов, описанных в этой главе, хотя некоторые из методов годятся только для числовых и буквенных ключей с общепринятым отношением порядка. Задача сортировки — найти такую перестановку записей р(Цр(2)...р(д») с индексами (1, 2,..., Х), после которой ключи расположились бы в порядке неубывания: К„„, <К„„« "<К,1,.

(1) Сортировка называется рсшойчиоой, если она удовлетворяет такому дополнительному условию, что записи с одинаковыми ключами остаются в прежнем порядке, т. е,, другими словами, р(!) < рО) для любых Кр»»! = Кр!Л и ! < 11 (2) В одних случаях придется физически перемещать записи в памяти так, чтобы их ключи были упорядочены; в других случаях достаточно создать вспомогательную таблицу, которая некоторым образом описывает перестановку и обеспечивает доступ к запэ!сям в соответствии с порядком нх ключей. Некоторые методы сортировки предполагают существование величин "оо" и "-оо" или одной из них. Величина "со" считается больше, а величина "— оо" меньше любого ключа: -оо < К; < оо для 1 <,~ < Ж. Эти величины используются в качестве искусственных ключей, а также граничных признаков.

Равенство в (3), вообще говоря, исключено. Если же оно, тем не менее, допускается, алгоритмы можно модифицировать так, чтобы они все-таки работали, хотя нередко при этом их изящество и эффективность отчасти утрачиваются. Обьгпео методы сортировки подразделяют на два класса: внутренние, когда все записи хранятся в быстрой оперативной памяти, и внешние, когда все записи в ней не помещаются. Методы внутренней сортировки обеспечивают большую гибкость при построении структур данных и доступа к иим, внешние же методы обеспечивают достижение нужного результата в "спартанских" условиях ограниченных ресурсов. Достаточно хороший общий алгоритм затрачивает на сортировку Ю записей время пропорционально Х !ок Ю; при этом требуется около!ок Х "проходовь по данным.

Как мы увидим в разделе 5.3.1, зто минимальное время, если записи расположены в произвольном порядке и сортировка выполняется попарным сравнением ключей. Так, если удвоить число записей, то и время при прочих равных условиях возрастет немногим более чем вдвое. (На самом деле, когда Ае неограниченно возрастает, время сортировки растет как Х(1ойХ)э, если все ключи различны, поскольку и размеры ключей увеличиваются, как минимум, пропорционально 1ок еэе с ростом еее; но практически К всегда остается ограниченным.) С другой стороны, если известно, что ключи являются случайными величинами с некоторым непрерывным распределением, то, как мы увидим ниже, сортировка может быть выполнена в среднем за 0()е') шагов. УПРАЖНЕНИЯ (чисть 1) 1. [МлО] Докажите, чта иэ законов трнхатамнн н транэятявнасти вытекает едииеелвеи. кисель перестановки р(1) р(2)...

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

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