Разработка программы сортировки данных на языке Turbo Pascal
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
? находится в квадратичной зависимости от числа элементов массива. Для больших объемов данных эти сортировки будут медленными, а начиная с некоторой величины, они будут слишком медленными, чтобы их можно было использовать на практике. Однако, они идеально подходят для сортировки небольшого количества элементов. Кроме этого, сортировка вставкой имеет два преимущества. Во-первых, она обладает естественным поведением, т.е. она выполняется быстрее для упорядоченного массива и дольше всего выполняется, когда массив упорядочен в обратном направлении. Это делает сортировку вставкой полезной для упорядочения почти отсортированных массивов. Во-вторых, элементы с одинаковыми ключами не переставляются: если список элементов сортируется с использованием двух ключей, то после завершения сортировки вставкой он по-прежнему будет упорядочен по двум ключам.
И, наконец, некоторые из простых методов можно расширить до более хороших методов или использовать их для улучшения более сложных. Например, таким как метод Шелла.
Таким образом все поставленные задачи курсовой работы полностью выполнены.
Глоссарий
№ п/пПонятиеОпределениеАлгоритм сортировкиэто алгоритм для упорядочения элементов в списке. В случае, когда элемент списка имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки. На практике в качестве ключа часто выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма. Внешняя сортировкаоперирует с запоминающими устройствами большого объёма, но с доступом не произвольным, а последовательным (упорядочение файлов), т.е. в данный момент мы видим только один элемент, а затраты на перемотку по сравнению с памятью неоправданно велики. Внутренняя сортировкаоперирует с массивами, целиком помещающимися в оперативной памяти с произвольным доступом к любой ячейке. Данные обычно упорядочиваются на том же месте, без дополнительных затрат. Времяосновной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью. Для упорядочения важны худшее, среднее и лучшее поведение алгоритма в терминах мощности входного множества A. Гетерогенный массивмассив, в разные элементы которого могут быть непосредственно записаны значения, относящиеся к различным типам данных. Гипертекстпринцип организации информационных массивов, при котором отдельные информационные элементы связаны между собой ассоциативными отношениями, обеспечивающими быстрый поиск необходимой информации и/или просмотр взаимосвязанных данных. Динамический массивмассив, размер которого может меняться во время исполнения программы. Естественность поведенияэффективность метода при обработке уже упорядоченных, или частично упорядоченных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше. Индекс массивацелое число, либо значение типа, приводимого к целому, указывающее на конкретный элемент массива. Информационный массивсовокупность зафиксированной информации, предназначенная для хранения и использования и рассматриваемая как единое целое. Сортировка простыми обменами, сортировка пузырькомпростой алгоритм сортировки. Для понимания и реализации этот алгоритм - простейший, но эффективен он лишь для небольших массивов. Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает - массив отсортирован. Сортировка простыми обменами, сортировка пузырькомпростой алгоритм сортировки. Для понимания и реализации этот алгоритм - простейший, но эффективен он лишь для небольших массивов. Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает - массив отсортирован. Сортировка слияниемалгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например - потоки) в определённом порядке. Сортировка Шеллаалгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Идея метода Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга. Иными словами - это сортировка вставками с предварительными "грубыми" проходами. Топологическая сортировкаупорядочивание вершин бесконтурного ориентированного графа согласно частичному порядку, заданному ребрами орграфа на множестве его вершин.
Список использованных источников
1.Джордейн, Р. Справочник программиста персональных компьютеров типа IBM PC, XT и AT: Пер. с англ. / Предисл. Н.В. Гайского, 2001 - 116с.
2.Довгаль, С.И. Персональные ЭВМ: Турбо-Паскаль V6.0, Объектное программирование, Локальные сети. (учебное пособие) /, С.И. Довгаль, Б.Ю. Литвинов, А.И. Сбитнев, - Киев: Информсистема сервис, 1993. - 210с.
.Дональд Кнут Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching - 2-е изд. - М.: "Вильямс", 2007. - С.824. - ISBN 5-8459-0082-4.
.М.М. Канаев, Т.З. Султанбекова, П?/p>