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

1. Напишите процедуру поиска трех минимальных элементов массива за один проход.

2. Напишите процедуру поиска k-й порядковой статистики при помощи неполного алгоритма QuickSort.

3. Выполните поиск медианы в массиве A= (48, 72, 3, 14, 35, 65, 88, 89, 95, 6, 5, 65, 21, 24, 77), используя неполный алгоритм QuickSort. В качестве разделяющего использовать первый элемент массива.

4. Выполните поиск образца ‘abbabab’ в строке ‘abbabbabbababb’, используя алгоритм Кнута, Морриса и Пратта.

5. Выполните поиск образца ‘bacab’ в строке ‘aacabacaabacabc’, используя алгоритм Бойера и Мура.

8. Заключение

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

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

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

9. Библиографический список

1. Вирт Н. Алгоритмы + структуры данных = программы. – М.: Мир, 1985. – 544 с.

2. Вирт Н. Алгоритмы и структуры данных. – М.: Мир, 1989. – 360 с.

3. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. – М.: Издательский дом «Вильямс», 2001. – 384 с.

4. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. – М.: МЦНМО, 2000. – 960 с.

5. Кнут Д. Искусство программирования. Т.3. Сортировка и поиск. – М.: Вильямс, 2002. – 720 с.

1В англоязычной литературе на равных используются термины «sorting» (сортировка) и «ordering» (упорядочение). Хотя слово «упорядочение» лучше отражает суть дела, на русском языке по каким-то причинам (возможно, фонетическим) гораздо чаще применяется термин «сортировка».

1Типичная ошибка, которую делают многие студенты, спеша запрограммироватьHeapSort, заключается в том, что вместо предварительного выбора большего из сыновей они выполняют сравнение и перестановкуa_kс каждым сыном по очереди. Пирамиду в конце концов построить удается, но времени на это уходит много. На рис.3.1это означает, что вместо одной ветви приходится перестраивать все поддерево вершиныa_k.

1В некоторых книгах АВЛ-деревья называют просто «сбалансированными деревьями». Это не совсем справедливо по отношению к другим типам деревьев, упомянутым в предыдущем абзаце, которые тоже неплохо сбалансированы.

1Многие полагают, что буква «B» здесь означает «Binary». Так утверждается даже в некоторых серьезных книгах. На самом деле, эти деревья вовсе не бинарные, а буква «B» происходит от фамилии «Bayer».

1Интересно отметить, чтоB⁺-деревья используются в файловой системеNTFSдля представления каталогов. Это позволяет уменьшить время поиска нужного файла, если общее число файлов в одном каталоге достигает нескольких сотен или тысяч.

1В знаменитой книге Д.Кнута [5] данная структура названа «trie», это искусственное слово есть гибрид «tree» (дерево) и «retrieve» (находить, извлекать). Переводчик первого издания предложил ввести на русском языке термин «бор», как намек на «дерево» и «выбор». Однако при переводе второго издания был предпочтен термин «нагруженное дерево».