Файл: Алгоритмы сортировки данных (Структура и алгоритмы обработки данных).pdf

Во второй главе данной курсовой работы особое внимание было уделено алгоритмам сортировки – внутренней и внешней. Как было выяснено алгоритмов сортировок очень много, и перед каждым пользователь предоставлен широкий их выбор. В данной курсовой работе внимание было уделено таким алгоритмам внутренней сортировки, как сортировка обменом, выбором, методом Шелла, Хоара, вставкой. Все эти алгоритма работают по-разному, какие-то быстрее, какие-то медленнее, например, алгоритм сортировки обменом, работает очень медленно, но при своей работе он не требует выделения дополнительной памяти ЭВМ. Сортировка выбором и включением, работают быстро, но только в массивах с малым количеством элементов. На смену этим простым методам пришли более усовершенствованные алгоритмы сортировок, такие как сортировки методом Шелла и Хоара. Сортировка методом Шелла очень сложна в использовании, но очень эффективна. Скорость работы данного алгоритма, также мала. Наиболее оптимальным алгоритмом, на сегодняшний день, является сортировка методом Хоара, которая и работает очень быстро, легка в использовании.

Также, были рассмотрены алгоритмы внешней сортировки, такие как сортировка простым и естественным слиянием. Алгоритм сортировки простым слиянием очень прост в использовании, но для своей работы требует выделения дополнительной памяти. Ему на смену пришел более усовершенствованный алгоритм естественным слиянием, который работает очень быстро.

Алгоритмов поиска данных, также как и сортировок существует очень много. В данной курсовой работе были рассмотрены следующие алгоритмы: линейный поиска, поиск делением пополам, прямой поиск строки, КМП-алгоритм, алгоритм Боуера-Мура. Линейный поиск – это простейший алгоритм поиска данных, и работает он очень медленно. Ему на смену пришел алгоритм поиска делением пополам, который работает очень быстро, но только в упорядоченном массиве. Для того, чтобы решить все эти недочеты первых двух алгоритмов были разработаны КМП-алгоритм, Алгоритма Боуера-Мура, прямой поиск строки, которые работают очень эффективно.

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

Список использованной литературы

1. Алексеев В.Е., Таланов В.А. Графы. Модели вычислений. Структуры данных: Учебник. – Нижний Новгород: Изд-во ННГУ, 2005. - 307 с.
2. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. – М.: Изд. дом “Вильямс”, 2001 г.- 384 с.
3. Ахо А. В., Хопкрофт Д. Э., Ульман Д. Д. Построение и анализ вычислительных алгоритмов: Пер.с англ. – М.: Мир, 1979. 312 с.
4. Вирт Н. Алгоритмы и структуры данных. М.: Мир, 1989. – 31 с.
5. Вирт Н. Алгоритмы и структуры данных.- СПб.: Невский диалект, 2001. - 352 с.
6. Голицына O.Л., Попов И.И. Основы алгоритмизации и программирования: учеб. Пособие - М: ФОРУМ, 2008 – с.16.
7. Давыдов В.Г. Программирование и основы алгоритмизации: Учеб. пособие / - 2-е изд., стер. - М.: Высш. шк., 2005. - 447 с.
8. Ивановский С.А. Структуры и алгоритмы обработки данных. Рабочая программа дисциплины. - СПб.: СПбГЭТУ, каф. МО ЭВМ, 2000. - с.79-94.
9. Ключарев А.А., Матьяш В.А., Щекин С.В. Структуры и алгоритмы обработки данных: Учебное пособие - СПбГУАП. СПб,2003 – с. 172.
10. Кищенко О.Н. Языки информационного обмена: материалы курса. - Новосибирск: НГТУ, 2007. – с.102.
11. Кнут Д. Искусство программирования. Том 3: Поиск и сортировка. М.: “Вильямс”, 2000 – 240 c.
12. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы. Построение и анализ. М.: МЦНМО, 2000- 132 с.
13. Лорин Г. Сортировка и системы сортировки. — М.: Изд-во Наука, Главная редакция физ.-мат. литературы, 1983 – с.16
14. Окулов С.М. Основы программирования. “Информатика”, №23, 2001 – 112 c.
15. Окулов С.M. Сортировка и поиск. “Информатика”, №33, 35, 2000 – 400 c.
16. Ставровский А.Б, Карнаух Т.А. Самоучитель. Первые шаги в программировании. М.: Изд. дом “Вильямс”, 2006 – с 230.
17. Царев Р.Ю. Учебное пособие по курсу «Структуры и алгоритмы обработки данных» - Красноярск: ИПЦ КГТУ, 2005. – с.30
18. Кузнецов С.Д., ИСП РАН, Центр Инф. Технологий [Электронный ресурс] - URL: http://citforum.ru/programming/theory/sorting/sorting1.shtml (дата обращения 10.07.2013г.)
19. Томас Ниман. Сортировка и поиск. Рецептурный справочник [Электронный ресурс] - URL: http://cs.mipt.ru/docs/comp/rus/programming/algorithms/niman_sort_poisk/main.pdf (дата обращения 12.07.2013г.)
20. Учебный курс «Введение в программирование». Лабораторная работа №1: Упорядочивание (сортировка) массивов. [Электронный ресурс] - URL: http://infoscool.narod.ru/Lab1_sort.pdf (дата обращения 15.07.2013)

21. Сундукова Т.О., Ваныкина Г.В. Структура и алгоритмы компьютерной обработки данных. - 2010 [Электронный ресурс] - URL: http://www.intuit.ru/department/algorithms/staldata/38/2.html (дата обращения: 16.08.2013г.)