Алгоритмы поиска и сортировки данных .

ВВЕДЕНИЕ
В последние годы программирование для персональных компьютеров стало во многом основным и ключевым моментом, определяющим успех многих инженерных проектов, а также объектом научного исследования. Научно доказано, что программы поддаются точному анализу, основанному на строгих математических рассуждениях, и что можно избежать многих традиционных для программистов ошибок, если осмысленно пользоваться научными методами и приемами.
ЭВМ приходится не только считывать данные и выполнять над ними определенные алгоритмы, но и хранить значительные объемы информации, к которой нужно быстро обращаться. Эта информация представляет собой абстракцию того или иного фрагмента реального мира и состоит из определенного множества данных, относящихся к какой-либо проблеме.
Алгоритм – это точное предписание, определяющее вычислительный процесс, ведущий от варьируемых начальных данных к искомому результату [2].
В процессе решения прикладных задач выбор подходящего алгоритма вызывает определенные трудности. Алгоритм должен удовлетворять следующим противоречащим друг другу требованиям: быть простым для понимания, перевода в программный код и отладки; эффективно использовать вычислительные ресурсы и выполняться по возможности быстро.
Если разрабатываемая программа, реализующая некоторый алгоритм, должна выполняться только несколько раз, то первое требование наиболее важно. В этом случае стоимость программы оптимизируется по стоимости написания (а не выполнения) программы. Если решение задачи требует значительных вычислительных затрат, то стоимость выполнения программы может превысить стоимость написания программы, особенно если программа выполняется многократно. Поэтому более предпочтительным может стать сложный комплексный алгоритм (в надежде, что результирующая программа будет выполняться существенно быстрее). Таким образом, прежде чем принимать решение об использовании того или иного алгоритма, необходимо оценить сложность и эффективность этого алгоритма.
Сложность алгоритма – это величина, отражающая порядок величины требуемого ресурса (времени или дополнительной памяти) в зависимости от размерности задачи.
Современная методология программирования предполагает, что оба аспекта программирования – запись алгоритма на языке программирования и выбор структур представления данных – заслуживают абсолютно одинакового внимания. Решение о том, как представлять данные, невозможно принимать без понимания того, какие алгоритмы будут к ним применяться, и наоборот, выбор алгоритма часто очень сильно зависит от строения данных, к которым он применяется.
Без знания структур данных и алгоритмов невозможно создать сколько-нибудь серьезный программный продукт.
Целью курсовой работы является изучение наиболее часто употребимых алгоритмов – алгоритмов поиска и сортировки данных.

Введение 3
1. Алгоритмы поиска 5
1.1. Поиск в линейных структурах 6
1.1.1. Последовательный (линейный) поиск 6
1.1.2. Бинарный поиск 9
1.2. Поиск по бинарному дереву 11
1.3. Хеширование 13
1.4. Поиск в тексте 17
1.4.1. Прямой поиск строки 17
1.4.2. Алгоритм Кнута, Мориса и Пратта 19
1.4.3. Алгоритм Боуера и Мура 21
Алгоритмы сортировки 22
1.5. Постановка задачи сортировки 22
1.6. Алгоритмы внутренней сортировки 23
1.6.1. Сортировка подсчетом 23
1.6.2. Сортировка простыми вставками 25
1.6.3. Сортировка выбором 26
1.6.4. Сортировка обменом (метод пузырька) 28
1.6.5. Сортировка Шелла 30
1.6.6. Быстрая сортировка Хоара 31
1.6.7. Пирамидальная сортировка 33
1.6.8. Сортировка слиянием фон Неймана 35
1.6.9. Сравнение алгоритмов внутренней сортировки 36
1.7. Алгоритмы внешней сортировки 40
1.7.1. Сортировка слиянием для файлов 41
1.7.2. Сортировка методом поглощения 42
1.7.3. Челночное балансное слияние 43
Заключение 47
Список использованной литературы 48

1. Аксёнова Е. А. Алгоритмы и структуры данных на С++/ Е. А. Аксёнова, А. В. Соколов.- Петрозаводск: Изд-во ПетрГУ, 2008. – 81 с.
2. Алгоритмизация и программирование: Учебно-методический комплекс. / А.Г. Сковиков. – Ульяновск: УлГТУ, 2006. – С. 108–110.
3. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. М.: Вильяме, 2001. 384 с.
4. АхоА., Хопкрофт Док., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.
5. Вирт Н. Алгоритмы + структуры данных = программы. М.: Мир, 1985.
6. Вирт Н. Алгоритмы и структуры данных. М: Мир, 1989. 360 с.
7. Гудман С, Хидетниеми С. Введение в разработку и анализ алгоритмов. М.: Мир, 1981.
8. Ключарев А. А., Матьяш В. А., Щекин С. В. Структуры и алгоритмы обработки данных: Учеб. пособие/ СПбГУАП. СПб., 2003. 172 с: ил.
9. Кнут Д. Е. Искусство программирования: В 3 т. М.: Вильяме, 2000.
10. Колдаев В. Д. Основы алгоритмизации и программирования: Учебное пособие / Под ред. проф. Л. Г. Гагариной. – М.: ИД «ФОРУМ»: ИНФРА-М, 2006. – 416 с: ил. – (Профессиональное образование).
11. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: Построение и анализ. М.: МЦНМО, 2001.
12. Седжвик Р. Фундаментальные алгоритмы на С++. Анализ/Структуры данных/Сортировка/Поиск. Киев: Изд-во \"Диа-Софт\", 2001.
13. Сибуя М., Ямамото Т. Алгоритмы обработки данных. М.: Мир, 1986.218 с.
14. Структуры и алгоритмы обработки данных/ В. А. Матъяш, В. А. Путилов, В. В. Филъчаков, С. В. Щекин. Апатиты: КФ ПетрГУ, 2000. 80 с.