Литература 7з

предпочтения. Этот файл ивляется входным для программы, котораи должна получить следующие результаты:

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

Всем пяти спискам должны предшествовать соответствующие заголовки. ПИТЕРАТУРА

DAHI. О. J., DIJKSTRA Е. W., HOARE С. А. R., Structured Program-ffling. - New York: Academic Press, 1972. [Имеется перевод: Дал О., Дейкстра Э., Хоор К., Структурное программирование. - М.: Мир, *TS75.]

12. HOARE С. А. R. Notes on Data Structuring. - Structured Programming. I-Dhl, Dijkstra, Hoare, 83-174. [Имеется перевод: Хоор К. Заметки о структурной^ ор5? анизации данных. - В кн.: Дал О., Дейкстра Э Хоор К. Структурное 1ф-ог?и1аммипрвание.М.- Мир. . Дгй.,-tP,Q 7 ,.3. JENSEN К.. WIRTH N. PksCAL,user Manual kn? Report-tctS Notes Ш Computer Science.-Berlin: Springer-Verlag 18 1974 ГИмеет ся перевод: Йенсен К., Вирт Н. ПАСКАЛЬ; Руководство для пользо-S?m N, n языка.-М.: Финансы и статистика. 19821 НУи. No 4,Т9П'?221-Й^ Refinement.-Comm.

МаиэЛ JjigP g i g Language PASCAL.-Лс/а fnformafica.

1.6. WIRTH N.On the Composition of Well-Structured Programs-Com-putlng Surveys. 6, No. 4. 1974, 247-259. -lograms. com

СОРТИРОВКА

2.1. ВВЕДЕНИЕ

Основная цель этой главы - показать на множестве пы меров, как используются структуры данных, описанные в ппе дыдущей главе, и продемонстрировать влияние выбранноб структуры данных на алгоритмы, выполняющие некоторй адаш!е^ Кроме того, сортировка служит хорошим примере того, что одна и та же цель может достигаться с помощыо различных алгоритмов, причем каждый из них имеет свов определенные преимущества и недостатки, котоп^р. чийг оценить ГЖ.з'ения кок'/ртной сит-hYi,.,.

Под сортировкой обычно понимают процесс перес/-лнов : объектов данного множества в определенном порядке. Tvi сортировки - облегчить последующий поиск элементов i сортированном множестве. В этом смысле элементы -/ ровки присутствуют почти во всех задачах. Упорядоч -- объекты содержатся в телефонных книгах, в ведомостям доходных налогов, в оглавлениях, в библиотеках, в слрзэ' на складах, да и почти всюду, где их нужно разысь;-и. 1* Даже маленьких детей приучают приводить вещи е^рл док , и они сталкиваются с некоторым видом сортс.:; задолго до того, как узнают что-либо об арифметике.

Следовательно, методы сортировки очень важны, особен,; при обработке данных. Казалось бы, что легче рассортг ... вать, чем набор данных? Однако с сортировкой. связ. . многие фундаментальные приемы построения алгоритмов, . торые и будут нас интересовать в первую очередь. Почти i . такие приемы встречаются в связи с алгоритмами copi . ровки. В частности, сортировка является идеальным прнь ром огромного разнообразия алгоритмов, выполняющих оЛ. и ту же задачу, многие из которых в некотором смыс являются оптимальными, а большинство имеет какие-ли преимущества по сравнению с остальными. Поэтому на пр мере сортировки мы убеждаемся в необходимости сравнитеЛ' ного анализа алгоритмов. Кроме того, здесь мы увидим, в' при помощи усложнения алгоритмов можно добиться зк тельного увеличения эффективности по сравнению с боЛ' простыми и очевидными методами.

Зависимость выбора алгоритмов от структуры ааннъи явление довольно частое, и в случае сортировки она настоль

2.1. Введение

пьна, что методы сортировки обычно разделяют на две ка-j.Qpm: сортировка массивов и сортировка (последователь-ык) файлов. Эти два класса часто называют внутренней glieuineu сортировкой, так как массивы располагаются во внутренней (оперативной) памяти ЭВМ; для этой памяти характерен быстрый произвольный доступ, а файлы хранятся в более медленной, но более вместительной внешней па-ддти, т. е. на запоминающих устройствах с механическим

Рис. 2.1. Сортировка массива.

;агредвижением (дисках и лентах). Это существенное разли- ;е можно наглядно показать на примере сортировки прону-= фованных карточек. Представление карточек в виде массива соответствует тому, что все они располагаются перед ! сортирующим так, что каждая карточка видна и доступна ;i(cM. рис. 2.1). Представление карточек в виде файла пред-йполагает, что видна только верхняя карточка из каждой СТОПКИ (см. рис. 2.2). Очевидно, что такое ограничение при- ведет к существенному изменению методов сортировки, но оно неизбежно, если карточек так много, что их число на столе не уменьшается.

Прежде всего мы введем некоторую терминологию и си- стему обозначений, которые будем использовать в этой главе. Нам даны элементы

1, Ог, ..., а^.

)! Сортировка означает перестановку этих элементов в таком порядке:

а,. %..... fe .

Что при заданной функции упорядочения f справедливо отно-:ение