Парадигма реализации типа интерфейс-клиент подробно, со множеством примеров описывается в книге Хансона (Hanson). Эта книга - замечательный справочник для тех программистов, которые намерены создавать устойчивый и переносимый код для больших систем.

Книги Кнута (Knuth), в особенности 1-й и 3-й тома, остаются авторитетным источником информации по свойствам элементарных структур данных. Книги Баеца-Йатса (Baeza-Yates) и Гоннета (Gonnet) содержат более современную информацию, подкрепленную внушительным библиофафическим перечнем. Седжвик (Sedgewick) и Флажолет (Flajolet) подробно освещают математические свойства деревьев.

Adobe Systems Incorporated, PostScript Language Reference Manual, econd edition, Addison-Wesley, Reading, MA, 1990.

R. Baeza-Yates and G. H. Gonnet, Handbook of Algorithms and Data Structures, second edition, Addison-Wesley, Reading,MA, 1984.

D. R. Hanson, С Interfaces and Implementations: Techniques for Creating Reusable Software, Addison-Wesley, 1997.

B. W. Kemighan and D. M. Ritchie, The С Programming Language, second edition, Prentice-Hall, Englewood Cliffs, JJ, 1988.

D. E. Knuth, The Art of Computer Programming. Volume I: Fundamental Algorithms, third edition, Addison-Wesley, Reading, MA, 1997; Volume 2: Seminumerical Algorithms, third edition, Addison-Wesley, Reading, MA, 1998; Volume 3: Sorting and Searching, second edition, Addison-Wesley, Reading,MA, 1998.

S. Meyers, Effective С++, second edition, Addison-Wesley, Reading, MA, 1996.

S. Meyers, More Effective С++, Addison-Wesley, Reading, MA, 1996.

R. Sedgewick and P. Flajolet, An Introduction to the Analysis of Algorithms, Addison-Wesley, Reading, MA, 1996.

T. A. Standish, Data Structures, Algorithms, and Software Principles in C, Addison-Wesley, 1995.

B. Stroustrup, The С++ Programming Language, third edition, Addison-Wesley, Reading MA, 1997.

Элементарные методы сортировки

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

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

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