Файл: Сортировка данных в массиве. Оценка эффективности метода (Архитектура программы).pdf

Введение

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

Предметом исследования данной работы является обзор алгоритмов сортировки данных различными методами.

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

Цель работы – разработать программу, способную демонстрировать возможности алгоритмов сортировки различными методами и получать экспериментальным путем количественные оценки их эффективности.

Для достижения поставленной цели поставлены следующие задачи:

1. Рассмотреть различные алгоритмы сортировки данных, выбрать несколько из них для реализации.
2. Разработать программный продукт, реализующий сортировку данных выбранными методами.
3. Протестировать разработанную программу.
4. Провести эксперименты по сортировке больших объемов данных всеми реализованными методами и выявить зависимости времени сортировки от количества сортируемой информации.

Данная работа состоит из трех глав и приложений.

Первая глава – вводная, в ней описывается постановка задачи и рассматриваются математические модели и алгоритмы выбранных методов сортировки данных.

Вторая глава посвящена процессу разработки приложения – здесь описывается процесс реализации выбранных алгоритмов сортировки и программной оболочки для демонстрации результатов для их последующего анализа.

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

В приложениях А–Д приведены исходные коды реализации выбранных методов сортировки, записанные на языке программирования высокого уровня C#.

Большой вклад при рассмотрении теоретических аспектов методов сортировки в рамках данного исследования составили труды Д. Э. Кнута. Книги "Искусство программирования" Д. Э. Кнута входят в золотой фонд мировой литературы по информатике и являются настольными книгами практически для всех, кто связан с программированием.

1. Обзор методов сортировки массивов данных

1.1. Понятие массива данных

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

Массивом данных называется совокупность однородных по структуре параметров, представленных в виде единой системы. Применительно к задачам программирования — это определение может быть уточнено: массив – это набор однотипных элементов, расположенных в памяти ЭВМ последовательно (друг за другом), доступ к которым осуществляется по их индексу (или ключу).

Таким образом, массив характеризуется тем, что ему присваивается определенное имя (идентификатор) и назначается в памяти ЭВМ конечная область памяти для хранения данных. Программист, обращаясь к конкретному элементу массива, указывает индекс требуемого элемента массива, а программа-интерпретатор по заданному индексу (зная начальный адрес размещения массива и размер одного элемента) находит нужную ячейку памяти и предоставляет доступ к элементу

1.2 Понятие и характеристики методов сортировки массивов

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

Математическая формальная постановка задачи сортировки массива описывается следующим образом: пусть дана последовательность элементов a₁, a₂, …, a_n, которую необходимо упорядочить. Каждый элемент будет иметь свой ключ сортировки k_i – поле, относительно которого будет осуществляться упорядочивание массива (помимо ключа элемент может содержать и другие поля, которые не влияют на сортировку и будут всегда принадлежать этому элементу). Задача сортировки формулируется как получение такой перестановки p₁, p₂, …, p_n элементов массива, в результате которой ключевые записи элементов этого массива будут располагаться в возрастающем (или убывающем) порядке:

k_p1 ≤ k_p2 ≤ … ≤ k_pn (k_p1 ≥ k_p2 ≥ … ≥ k_pn).

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

Первые попытки исследования алгоритмов сортировки данных были предприняты в середине XX века с появлением первых промышленных ЭВМ и продолжаются и в настоящее время. Данному вопросу посвящен знаменитый труд профессора Стенфордского университета Дональда Кнута «Искусство программирования», и сегодня не потерявший своей актуальности.

Таким образом, характер исходных данных в сортируемом массиве может оказывать существенное влияние на выбор метода сортировки. Задача выбора метода сортировки также нетривиальна и важна, поскольку от правильно выбранного метода сортировки зависят используемые машинное время и ресурсы. Причем затраты существенно увеличиваются с ростом размера сортируемого массива. В качестве примера можно привести решение задачи сортировки массива элементов из 10000 элементов, которые изначально расположены в требуемом порядке, кроме последних двух. В этом случае не требуется сортировать весь массив, а по сути нужно поменять местами только 2 последних значения. Простейшие методы сортировки не будут учитывать такие моменты и будут перебирать все элементы в соответствии с заданным алгоритмом. Более оптимальные методы сортировки постараются минимизировать число операций перестановок и, соответственно, минимизировать время работы, тем самым будут более эффективными.

Основными параметрами, которые определяют эффективность методов сортировки, являются:

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

В ходе выполнения алгоритмов сортировки данных временной ресурс ЭВМ занимают две основные операции: сравнение элементов массива по выбранному для сортировки ключу и внутреннее перемещение, перераспределение элементов массива. При этом количество выполняемых операций сравнения и число перестановок элементов массива зависят от размера входного массива.

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

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

В зависимости от приёма, лежащего в основе методов сортировки, принято делить их на три основных класса:

• сортировка выбором;
• сортировка включением;
• сортировка обменом.

В данной работе будет проведено исследование следующих алгоритмов сортировки: выбора, обмена (пузырьковая), вставками, Шелла, быстрая.

1.3 Сортировка методом выбора

Сортировка методом выбора является наиболее простой в исполнении. Такая сортировка основана на поиске оптимального (наибольшего или наименьшего) элемента и размещении его в начале сортируемого массива.

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

При сортировке выбором методом упорядоченный массив записей размещается на том же участке памяти, что и исходный.

Таким образом, алгоритм сортировки методом выбора сводится к многократному поиску оптимального элементов в неотсортированной части массива, которая с каждой итерации уменьшается от N до 2 (здесь N – длина массива).

Оценка временной сложности алгоритма сортировки методом выбора составляет O(N) = N².

1.4 Сортировка методом обмена

Сортировка методом обмена основана на серии повторяющихся проходов по сортируемой последовательности. На каждом шаге при последовательном проходе по массиву соседние элементы сравниваются попарно и меняются местами в случае, если их порядок не соответствует целевому. Подобные проходы выполняются N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что будет говорить о полной отсортированности массива.

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

Основное достоинство этого алгоритма – простота понимания и реализации. Однако считается, что данный алгоритм эффективен только для маленьких массивов.

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