Анализ эффективности методов сортировки данных в языке Turbo Pascal. Разработка эскизного и технического проекта программы. Сортировка без и с использованием дополнительной памяти, за исключением небольшого стека (массива). Сортировка связанных списков.
Аннотация к работе
2.3 Постановка задачи сортировки и методы ее решения 2.4 Сортировка пузырьковым методом 2.5 Сортировка выборомГлоссарийУсловие задачи: Разработать проект, который позволит сортировать заданный линейный массив целых чисел различными методами, например, методом линейной сортировки, пузырька, Шелла и др.В данном задании необходимо разработать вычислительную программу, представляющую собой проект для осуществления сортировки различными методами, не менее трех.Сортировка данных - это процесс изменения порядка расположения элементов в некоторых упорядоченных структурах данных таким образом, чтобы обеспечить возрастание или убывание числового значения элемента данных или определенного числового параметра, связанного с каждым элементом данных (ключа), при переходе от предыдущего элемента к последующему. Ниже показана самая простая форма программы сортировки методом пузырька: {сортировка пузырьковым методом} procedure Bubble (var item: DATAARRAY; count: integer); Например, если не учитывать время операций обмена, выполняемых для перестановки неупорядоченных элементов, то тогда при выполнении одной операции сравнения в течение 0,001 секунд сортировка десяти элементов займет 0,05 секунд, сортировка ста элементов займет 5 секунд, а сортировка 1000 элементов займет 500 секунд. Можно, например, заметить, что сортировка пузырьковым методом обладает одной особенностью: расположенный не на своем месте в конце массива элемент (например, элемент "а" в массиве "dcab") достигает своего места за один проход, а элемент, расположенный в начале массива (например, элемент "d"), очень медленно достигает своего места. В отличие от сортировки пузырьковым методом и сортировки выбором число операций сравнения для сортировки вставкой зависит от исходной упорядоченности массива элементов.В ходе курсовой работы была написана программа на языке Turbo Pascal, позволяющая сортировать линейный массив 4-мя методами: 1) Методом пузырька; Были рассмотрены вопросы: постановка задачи о сортировке, основные алгоритмы сортировки, их принципы действия и области применения. Рассмотренные в данной курсовой работе методы сортировки имеют как преимущества, так и недостатки. Так, сортировка большого числа элементов пузырьковым методом, методом вставки или выбора потребует много времени, т.к. время выполнения сортировки находится в квадратичной зависимости от числа элементов массива. Во-вторых, элементы с одинаковыми ключами не переставляются: если список элементов сортируется с использованием двух ключей, то после завершения сортировки вставкой он по-прежнему будет упорядочен по двум ключам.
План
Содержание
Введение
1. Разработка эскизного и технического проекта программы (ГОСТ 19.404-79)
1.1 Задание
1.2 Назначение и область применения
Вывод
ГлоссарийВ ходе курсовой работы была написана программа на языке Turbo Pascal, позволяющая сортировать линейный массив 4-мя методами: 1) Методом пузырька;
2) Методом вставок;
3) Методом выбора;
4) Методом Шелла.
Были рассмотрены вопросы: постановка задачи о сортировке, основные алгоритмы сортировки, их принципы действия и области применения.
Рассмотренные в данной курсовой работе методы сортировки имеют как преимущества, так и недостатки. Выбор того или иного алгоритма сортировки зависит от конкретной задачи.
Так, сортировка большого числа элементов пузырьковым методом, методом вставки или выбора потребует много времени, т.к. время выполнения сортировки находится в квадратичной зависимости от числа элементов массива. Для больших объемов данных эти сортировки будут медленными, а начиная с некоторой величины, они будут слишком медленными, чтобы их можно было использовать на практике. Однако, они идеально подходят для сортировки небольшого количества элементов. Кроме этого, сортировка вставкой имеет два преимущества. Во-первых, она обладает естественным поведением, т.е. она выполняется быстрее для упорядоченного массива и дольше всего выполняется, когда массив упорядочен в обратном направлении. Это делает сортировку вставкой полезной для упорядочения почти отсортированных массивов. Во-вторых, элементы с одинаковыми ключами не переставляются: если список элементов сортируется с использованием двух ключей, то после завершения сортировки вставкой он по-прежнему будет упорядочен по двум ключам.
И, наконец, некоторые из простых методов можно расширить до более хороших методов или использовать их для улучшения более сложных. Например, таким как метод Шелла.
Таким образом все поставленные задачи курсовой работы полностью выполнены.
Глоссарий
№ п/п Понятие Определение
Алгоритм сортировки это алгоритм для упорядочения элементов в списке. В случае, когда элемент списка имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки. На практике в качестве ключа часто выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма.
Внешняя сортировка оперирует с запоминающими устройствами большого объема, но с доступом не произвольным, а последовательным (упорядочение файлов), т.е. в данный момент мы "видим" только один элемент, а затраты на перемотку по сравнению с памятью неоправданно велики.
Внутренняя сортировка оперирует с массивами, целиком помещающимися в оперативной памяти с произвольным доступом к любой ячейке. Данные обычно упорядочиваются на том же месте, без дополнительных затрат.
Время основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью. Для упорядочения важны худшее, среднее и лучшее поведение алгоритма в терминах мощности входного множества A.
Гетерогенный массив массив, в разные элементы которого могут быть непосредственно записаны значения, относящиеся к различным типам данных.
Гипертекст принцип организации информационных массивов, при котором отдельные информационные элементы связаны между собой ассоциативными отношениями, обеспечивающими быстрый поиск необходимой информации и/или просмотр взаимосвязанных данных.
Динамический массив массив, размер которого может меняться во время исполнения программы.
Естественность поведения эффективность метода при обработке уже упорядоченных, или частично упорядоченных данных. Алгоритм ведет себя естественно, если учитывает эту характеристику входной последовательности и работает лучше.
Индекс массива целое число, либо значение типа, приводимого к целому, указывающее на конкретный элемент массива.
Информационный массив совокупность зафиксированной информации, предназначенная для хранения и использования и рассматриваемая как единое целое.
Сортировка простыми обменами, сортировка пузырьком простой алгоритм сортировки. Для понимания и реализации этот алгоритм - простейший, но эффективен он лишь для небольших массивов. Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает - массив отсортирован.
Сортировка простыми обменами, сортировка пузырьком простой алгоритм сортировки. Для понимания и реализации этот алгоритм - простейший, но эффективен он лишь для небольших массивов. Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает - массив отсортирован.
Сортировка слиянием алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например - потоки) в определенном порядке.
Сортировка Шелла алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Идея метода Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определенном расстоянии друг от друга. Иными словами - это сортировка вставками с предварительными "грубыми" проходами.
Топологическая сортировка упорядочивание вершин бесконтурного ориентированного графа согласно частичному порядку, заданному ребрами орграфа на множестве его вершин.
Список литературы
Введение
Необходимость отсортировать какие-либо величины возникает в программировании очень часто. К примеру, входные данные подаются "вперемешку", а нашей программе удобнее обрабатывать упорядоченную последовательность. Существуют ситуации, когда предварительная сортировка данных позволяет сократить содержательную часть алгоритма в разы, а время работы - в десятки раз.
Однако верно и обратное. Сколь бы хорошим и эффективным ни был выбранный вами алгоритм, но если в качестве подзадачи он использует "плохую" сортировку, то вся работа по его оптимизации оказывается бесполезной. Неудачно реализованная сортировка входных данных способна заметно понизить эффективность алгоритма в целом. В курсовой работе наша речь будет идти об эффективности различных методов сортировки данных в языке Turbo Pascal.
Объект и предмет исследования - методы сортировки данных, используемые в языке Turbo Pascal.
Целью данного исследования является анализ эффективности различных методов сортировки данных в языке Turbo Pascal.
Вообще говоря, методы сортировки делятся на три типа: 1. методы сортировки, которые сортируют без использования дополнительной памяти, за исключением, возможно, небольшого стека и/или массива;
2. методы, которые используют для сортировки связанные списки и поэтому используют N дополнительных указателей хранящихся в памяти;
3. а также методы, которые нуждаются в дополнительной памяти для хранения копии сортируемого файла.
1. Разработка эскизного и технического проекта программы (ГОСТ 19.404-79)1. Джордейн, Р. Справочник программиста персональных компьютеров типа IBM PC, XT и AT: Пер. с англ. / Предисл. Н.В. Гайского, 2001 - 116с.
3. Дональд Кнут Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching - 2-е изд. - М.: "Вильямс", 2007. - С.824. - ISBN 5-8459-0082-4.
4. М.М. Канаев, Т.З. Султанбекова, Программирование на языке TP: учебное пособие. Махачкала: ДГТУ, 2010 г.
5. Малыхина М.П. Программирование на языке высокого уровня Turbo Pascal. - издательство "СПБ: БХВ-Петербург", 2006.
6. Меженный О. А.,Turbo Pascal Краткое руководство. Москва 2006 г.
7. Моргун Александр Николаевич Программирование на языке Паскаль (Pascal). Основы обработки структур данных. - М.: "Диалектика", 2005. - С.576. - ISBN 5-8459-0935-X.
8. Павловская, Т.А. Паскаль. Программирование на языке высокого уровня: Учебник для вузов/ Т.А. Павловская - СПБ.: Питер, 2006. - 123 с.
9. Перминов, О.Н. Программирование на языке Паскаль. / О.Н. Перминов - М.: Радио и связь, 1988. - 156с.
10. Порублев Илья Николаевич, Ставровский Андрей Борисович Алгоритмы и программы. Решение олимпиадных задач - М.: "Вильямс", 2007. - С.480. - ISBN 978-5-8459-1244-2.
11. Прайс, Д. Программирование на языке Паскаль: Практическое руководство. Пер. с англ. /Д. Прайс - М.: Мир, 1987. - 232с.
12. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS - 2-е изд. - М.: "Вильямс", 2006. - С.1296. - ISBN 5-8459-0857-4.
13. Уоррен, Д. Алгоритмические трюки для программистов. Пер. с англ. [Текст] / Д. Уоррен, С. Генри - М.: Вильямс, 2007, - -288с, 14. Фролов В.В. Turbo Pascal 7.0 Учебный курс. Москва, 2011 г.
15. Эллилот Б. Коффман, Turbo Pascal (5-е издание). Москва 2010 г.