1. Введение 5

1.1. Содержание и структура пособия 5

1.2. Задачи поиска в информатике 6

1.3. Задача поиска в таблице 6

2. Поиск в массивах 8

2.1. Линейный поиск 8

2.2. Бинарный поиск 11

2.3. Вопросы и упражнения 12

3. Алгоритмы сортировки массивов 13

3.1. Задачи сортировки таблиц и массивов 13

3.2. Простые алгоритмы сортировки 13

3.3. Алгоритм Шелла (ShellSort) 16

3.4. Алгоритм быстрой сортировки (QuickSort) 17

3.5. Алгоритм пирамидальной сортировки (HeapSort) 20

3.6. Алгоритмы сортировки слиянием (MergeSort) 24

3.7. Задача внешней сортировки 26

3.8. Сравнение алгоритмов сортировки 28

3.9. Вопросы и упражнения 30

4. Сортировка и поиск с использованием деревьев 31

4.1. Задача поиска со вставкой 31

4.2. Бинарные деревья поиска 32

4.3. АВЛ-деревья 37

4.4. Страничные деревья поиска 40

4.5. B-деревья 44

4.6. Использование B-деревьев в базах данных 49

4.7. Вопросы и упражнения 50

5. Специальные методы сортировки и поиска 50

5.1. Поразрядная сортировка 51

5.2. Поиск в словаре и нагруженные деревья 54

5.3. Вопросы и упражнения 56

6. Хеширование 57

6.1. Основные понятия хеширования 57

6.2. Способы построения хеш-функций 59

6.3. Методы разрешения коллизий 65

6.4. Эффективность хеширования и сравнение с другими методами поиска 68

6.5. Вопросы и упражнения 70

7. Дополнительные вопросы поиска 70

7.1. Определение порядковых статистик 70

7.2. Задача поиска в строке 72

1. Введение

   1. Содержание и структура пособия

Это пособие посвящено одному из наиболее интересных и практически ценных разделов информатики – алгоритмам и структурам данных, используемым для решения задач сортировки и поиска.

Цель пособия – в компактном объеме дать студентам достаточно широкий обзор различных вариантов постановки задач сортировки и поиска и при этом рассмотреть основные алгоритмы решения этих задач с такой степенью подробности, которая позволила бы использовать полученные знания в практической работе.

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

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

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

В разделе 7 рассматриваются две задачи, лежащие несколько в стороне от проблемы поиска в таблицах, но тесно связанные с ней по постановке и по методам решения. Это задача определения порядковых статистик и задача поиска подстроки в строке.

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

Излагаемые алгоритмы и методы являются результатом исследований, проводившихся многими специалистами в течение нескольких десятилетий. В книгах [1, 2, 3, 4, 5] можно найти более подробное описание этих алгоритмов, их теоретический анализ, а также много интересных алгоритмов и структур, не упомянутых в данном пособии.

Учебное пособие не является справочником по алгоритмам, поэтому тексты программ на Паскале или на псевдокоде приводятся только в тех случаях, когда это проще, чем объяснить детали алгоритма на словах. В остальных случаях реализация алгоритма оставлена для выполнения студентами в рамках лабораторных или самостоятельных занятий.

2. Задачи поиска в информатике

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

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

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