Учебное пособие C#. Алгоритмы и структуры данных н. А. Тюкачев, В. Г. Хлебостроев издание третье, стереотипное 1 / 23

В
ЫВОДЫ
 
Алгоритмы поиска и сортировки являются фундаментальными алго-
ритмами информатики. Скорость их выполнения очень часто оказывает ре-
шающее влияние на скорость работы различных программных систем. Имен-
но поэтому их разработке и анализу уделяется столь пристальное влияние. 
Одним из наиболее полных является обзор методов сортировки и поиска, 
представленный в монографии [24]. В данной главе мы ограничились рас-
смотрением лишь наиболее распространенных из них. Среди рассмотренных 
были алгоритмы с различной временной эффективностью: O(1) для поиска в 
хеш-таблице, O(log
2
N) для бинарного поиска, O(N) для сортировки Шелла и 
сортировки подсчетами, O(N·log
2
N) для сортировки выбором, O(N
2
) для сор-
тировок включениями и обменом. Выбор того или иного алгоритма должен 
определяться выбором между требованиями к скорости выполнения про-
граммы и сложностью реализации алгоритма. 
Для повышения эффективности операций поиска в больших массивах 
данных рекомедуется использовать технологию хеширования, позволяющую 
за счет некоторого избыточного расходования ресурса памяти существенно 
повысить скорость поиска. Для работы с хеш-таблицами рекомендуется ис-
пользовать готовое решение Microsoft – класс Hashtable. 
21 / 23

---

45 
У
ПРАЖНЕНИЯ
 
1. Используя класс Timing (глава 1), проведите экспериментальное 
изучение зависимости времени выполнения от размера массива для 
алгоритмов сортировки методом включения и методом Шелла. 
2. То же для алгоритмов простого и бинарного поиска.
3. Каков будет результат выполнения алгоритма бинарного поиска для 
неупорядоченного массива? 
4. Создайте приложение, в котором подсчитывается количество срав-
нений при выполнении поиска в массиве. Подсчитайте количество 
сравнений при использовании алгоритмов простого поиска, поиска с 
барьером и бинарного поиска для одних и тех же исходных данных. 
5. В приложении «Телефонный справочник» реализуйте разрешение 
коллизий методом цепочек.
6. Используя класс Hashtable, создайте справочник столиц стран ми-
ра. В качестве ключа используйте название страны, а в качестве зна-
чения – название ее столицы. 
22 / 23

---

46