Лабораторная работа № 2 Операции над алгебраическими структурами Изучение методов сортировки данных

Цель работы: изучение наиболее известных методов сортировки данных и их использование на примерах конкретных задач.

1.1 Теоретическая часть

Для дискретного анализа характерно, что самые простые, казалось бы, ничем не примечательные задачи могут быть предметом серьёзного научного исследования. Здесь мы рассматриваем одну из таких простых задач, которая часто встречается в приложениях, называется задачей сортировки и до сих пор остается интересной.

При рассмотрении данного круга задач необходимо предварительно изучить тему «Множества и отношения». Рефлексивное, транзитивное, но антисимметричное отношение R на множестве A называется частичным порядком. Частичный порядок важен в тех ситуациях, когда мы хотим как-то охарактеризовать старшинство. Иными словами, решить при каких условиях можно считать, что один элемент множества превосходит другой.

Примеры частичных порядков.

«» на множестве вещественных чисел;

«» на подмножествах универсального множества;

«…делит…» на множестве натуральных чисел.

Множества с частичным порядком принято называть частично упорядоченными множествами (ч. у. м.).

Если R – отношение частичного порядка на множестве A, то при х y и xRy мы называем x предшествующим элементом или предшественником, а y – последующим. У произвольно взятого элемента y может быть много предшествующих элементов. Однако если x предшествует y, и не существует таких элементов z, для которых xRz и zRy, x называется непосредственным предшественником (иначе говорят, что y покрывает x) и обозначается x<y [3].

Линейным порядком на множестве A называется отношение частичного порядка, при котором из любой пары элементов можно выделить предшествующий и последующий.

Постановка задачи: пусть задано конечное множество А, состоящее из n элементов a_i, на нём задано отношение линейного порядка Р.

Требуется перенумеровать элементы А числами от 1 до n таким образом, чтобы из того, что i<j следовало (a_i, a_j) Є P. Выполнение этой задачи называется сортировкой массива данных [3].

Способы сравнения могут быть очень разнообразными, но в большинстве случаев они исходят из двух базовых элементарных упорядочений: упорядочение чисел по значению и упорядочение слов по алфавиту.

Потребность в сортировке больших объёмов данных ощущалась очень давно, например, в комплекте счётно-аналитических машин Холлерита была специальная сортирующая машина.

Во многих задачах требуется иметь данные, расположенные в порядке возрастания или в порядке убывания. Такое упорядочение в программировании называется сортировкой. Сортировка применяется во многих задачах. Существуют различные методы сортировки: одни из них просты, но более медленные, другие быстрые, но более сложные. Одни сортируют каждый массив заново, другие распознают уже упорядоченные части массива и поэтому работают быстрее.

Выдающийся специалист по программированию Д. Кнут посвятил сортировке и поиску данных почти весь второй том трудов «Искусство программирования для ЭВМ» [4].

Сортировка данных – обработка информации, в результате которой элементы её (записи) располагаются в определённой последовательности в зависимости от значения некоторых признаков элементов, называемых ключевыми.

Наиболее распространёнными видами сортировки данных являются упорядочение массива записей – расположение записей сортируемого массива данных в порядке монотонного изменения значения ключевого признака. Сортировка данных позволяет сократить в десятки раз продолжительность решения задач, связанных с обработкой больших массивов записей. Такое ускорение происходит за счёт сокращения времени поиска записей с определёнными значениями ключевых признаков. Упорядочение осуществляется в процессе многократного просмотра исходного массива.

Одними из важнейших процедур обработки структурированной информации являются сортировка и поиск. Сортировкой также называют процесс перегруппировки заданной последовательности (кортежа) объектов в некотором определенном порядке. Определенный порядок (например, упорядочение в алфавитном порядке, по возрастанию или убыванию количественных характеристик, по классам, типам и т. п.) в последовательности объектов необходим для удобства работы с этими объектами. В частности, одной из целей сортировки является облегчение последующего поиска элементов в отсортированном множестве. Под поиском подразумевается процесс нахождения в заданном множестве объекта, обладающего свойствами или качествами задаваемого априори эталона (или шаблона).

Например, требуется решить задачу: даны целые числа x, a₁, a₂, …, a_n (n>0). Определить, каким по счёту идёт в последовательности a₁, a₂, …, a_n член, равный x. Если такого члена нет, то предусмотреть соответствующее сообщение.

В этом примере мы сталкиваемся с задачей поиска. «Одно из наиболее часто встречающихся в программировании действий – поиск. Он же представляет собой идеальную задачу, на которой можно испытывать различные структуры данных…» – пишет Н. Вирт [14]. Теория поиска – важный раздел теории информации.

Очевидно, что с отсортированными (упорядоченными) данными работать намного легче, чем с произвольно расположенными. Упорядоченные данные позволяют эффективно их обновлять, исключать, искать нужный элемент и т. п. Достаточно представить, например, словари, справочники, списки кадров в неотсортированном виде и сразу становится ясным, что поиск нужной информации является труднейшим делом.