Преподаватель который помогает студентам и школьникам в учёбе.

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

Содержание:

Введение

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

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

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

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

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

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

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

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

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

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

В приложениях А–Д приведены исходные коды реализации выбранных методов сортировки, записанные на языке программирования высокого уровня 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 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что будет говорить о полной отсортированности массива.

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

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

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

Метод сортировки обменами впоследствии стал основой некоторых более совершенных методов. Например, на его основе построены алгоритмы шейкерной, пирамидальной и быстрой сортировки.

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

1.5 Сортировка методом вставок

Метод сортировки вставками основан на поиске позиции для очередного элемента в отсортированном массиве и перемещении его в эту позицию.

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

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

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

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

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

1.6 Сортировка методом Шелла

Сортировка методом Шелла относится к разряду методов сортировки вставками и использует в своей реализации метод сортировки простыми вставками. Алгоритм, предложенный Д. Шеллом в 1959 году, направлен на оптимизацию скорости сортировки метода простыми вставками – при его применении реализуется механизм осуществления ряда групповых и одной конечной сортировки. При этом групповые сортировки расставляют элементы последовательности так, чтобы последняя, финальная сортировка была произведена за наименьшее число перестановок.

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

вначале осуществляется сортировка простыми вставками каждых 8-ми групп из 2-х элементов (n1, n9), (n2, n10), …, (n8, n16);
затем осуществляется сортировка вставками каждой из четырёх групп по 4 элемента (n1, n5, n9, n13), …, (n4, n8, n12, n16);
затем осуществляется сортировка вставками двух групп по 8 элементов, начиная с (n1, n3, n5, n7, n9, n11, n13, n15);
на конечном шаге производится сортировка вставками всех 16 элементов.

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

Наглядно принцип работы алгоритма Шелла проиллюстрирован на рисунке 1.1.

Рисунок 1.1 – Пример действия алгоритма Шелла

Алгоритм Шелла также имеет название метода сортировки с убывающим смещением, т.к. при каждом проходе выполняется смещение таким образом, что сортируемые записи отстоят друг от друга на величину этого смещения.

Величина смещения при выполнении частных сортировок является предметом споров, при этом в каждой конкретной ситуации предложенные варианты могут быть оправданы – это зависит от характеристик сортируемой последовательности. В настоящее время известными являются последовательности длин промежутков, предложенные Седжвиком, Марцина Циура, Хиббардом, Праттом, и др. Соблюдение каждой из этих последовательностей изменяет вычислительную сложность алгоритма. Принцип сортировки Шелла продуктивен при организации параллельных вычислений.

Были проведены многочисленные исследования по вопросу, какова должна быть последовательность расстояний D между сортируемыми элементами в зависимости от прохода. В итоге в любом случае исходный набор значений сортируется вставками, поэтому теоретически не имеет значение величина последовательности. Величина последовательности D является причиной известной неопределенности алгоритма Шелла.

Наиболее простой случай – принять D равным N/2 (N – длина сортируемой последовательности). В этом случае в худшем варианте сложность алгоритма составит O(N) = N².
Хиббард предложил в качестве последовательности длин промежутков использовать все значения 2ⁱ – 1, меньшие либо равные N, iN. В таком случае сложность алгоритма будет составлять O(N) = N^3/2.

Установлено, что производительность алгоритма сортировки Шелла приблизительно пропорциональна величине O(N²), однако число перестановок в сравнении с методом простыми вставками или пузырьком становится меньше за счет подготовительных проходов.

Дополнительная память для сортировки Шелла не требуется (если не считать затраты на хранение счетчиков, временных переменных, и т.д.).

Основная значимая настройка алгоритма Шелла, которая позволяет управляет его производительностью – размер шага предварительных прогонов D. Выбор этой величины существенно влияет на производительность алгоритма в целом, позволяя достигать величин, пропорциональных: от ~ O(N^7/6) в лучшем случае до ~ O(N^4/3) в худшем.

1.7 Метод быстрой сортировки

Алгоритм быстрой сортировки основан на стратегии «разделяй и властвуй» и состоит из следующих шагов:

В исходном массиве выбирается некоторый элемент, который будет называться опорным элементом. С позиции корректности выполнения алгоритма в качестве опорного элемента может быть выбран любой, однако с точки зрения повышения эффективности опорным элементом следует выбирать медиану. Наиболее известными стратегиями являются: выбор постоянно одного и того же элемента, выбор случайного элемента.
Выполняется операция разделения массива: массив перегруппируется так, чтобы все элементы, меньшие или равные опорному элементу, оказались слева от него, а все элементы, большие опорного — справа от него (при сортировке по возрастанию). Алгоритм разделения массива выполняется следующим образом:
Два индекса — l и r, приравниваются к минимальному и максимальному индексу разделяемого массива соответственно.
Вычисляется индекс опорного элемента m.
Индекс l последовательно увеличивается до m до тех пор, пока l-й элемент не превысит опорный.
Индекс r последовательно уменьшается до m до тех пор, пока r-й элемент не окажется меньше либо равен опорному.
Если r = l — найдена середина массива — операция разделения закончена, оба индекса указывают на опорный элемент.
Если l < r — найденную пару элементов нужно обменять местами и продолжить операцию разделения с тех значений l и r, которые были достигнуты. Следует учесть, что если какая-либо граница (l или r) дошла до опорного элемента, то при обмене значение m изменяется на r-й или l-й элемент соответственно.
Рекурсивно выполняется упорядочивание обоих массивов, расположенных слева и справа от опорного элемента. Базой рекурсии являются наборы из одного или двух элементов. Первый возвращается в исходном виде, во втором, при необходимости, сортировка сводится к перестановке двух элементов.

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

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

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

Вывод по главе 1

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

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

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

Разработка программы, демонстрирующей эффективность сортировки

Описание методов и средств разработки программы

Для разработки программного обеспечения тестирования методов сортировки массивов (ПО ТМСМ) в настоящей работе был использован язык программирования высокого уровня (ЯПВУ) C#. NET. ЯПВУ C# нацелен на повышение продуктивности разработчиков. Для этого в языке соблюдается баланс между простотой, выразительностью и производительностью. Универсальность и популярность ЯПВУ C# обеспечивается за счет следующих возможностей:

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

Для разработки визуальных приложений используются специальные среды разработки – IDE (Integrated Development Environment), которые предлагают удобные редакторы визуальных форм, палитру компонентов интерфейса и редактор исходного кода. Построение графического приложения ПО ТМСМ было выполнено с помощью редактора визуальных форм IDE Visual Studio 2015.

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

2. Архитектура программы

2.1 Объектная структура программы

Объектная структура ПО ТМСМ приведена на рисунке 2.1 в виде UML-диаграммы классов (все UML-диаграммы в данной работе выполнены с помощью CASE-системы Star UML).

Рисунок 2.1 – Объектная структура ПО ТМСМ

Объектная структура ПО ТМСМ включает следующие классы:

Статический класс ArraySorter – класс, в котором собраны все рассматриваемые методы сортировки (SortByShell – сортировка Шелла, BubbleSort – сортировка обменом, InsertionsSort – сортировка вставками, SelectionSort – сортировка выбором, QuickSort – быстрая сортировка), метод генерации массива GetArrayWithSortDegree, а также поля для хранения результатов тестирования метода сортировки: OperationsCount – количество операций, произведенных в ходе сортировки (считаются все операции присваивания, осуществляемые с элементами массивов), фактическое время выполнения сортировки в миллисекундах.
Класс главной формы пользовательского интерфейса MainSorterForm, предоставляющий пользователю средства для настройки исходных данных для проведения экспериментов и средства для визуализации результатов экспериментов. Класс содержит методы обработчиков событий пользовательского интерфейса (на диаграмме не показаны) и методы запуска экспериментов двух типов: Experiment1_GO – эксперимент сортировки массивов разными методами с изменением размера массивов, Experiment2_GO – эксперимент сортировки массивов разными методами с изменением степени исходной упорядоченности массивов. Все результаты произведенных экспериментов сохраняются в списковых структурах типа ResPoint.
Класс ResPoint – класс, представляющий результат эксперимента одной сортировки (любым из метолов). Класс содержит поля: X – аргумент (в зависимости от типа эксперимента: размер массива или его исходная степень упорядоченности), Y1 – количество произведенных операций (присваивания, относящиеся к массивам), Y2 – фактическое время выполнения эксперимента в миллисекундах.

2.2 Описание программных модулей

На рисунке 2.2 приведен компонентный состав модулей ПО ТМСМ в виде UML-диаграммы компонентов:

ArraySorter.cs – модуль, включающий исполнение класса-сортировщика и реализацию всех рассматриваемых методов сортировки (см. п.2.2.1).
ResPoint.cs – модуль класса представления точечного результата сортировки (см. п.2.2.1).
MainSorterForm.cs – модуль пользовательского интерфейса ПО ТМСМ (см. п.2.2.1).
.NET Framework 4.5 – пакет библиотек .NET, требуемых для функционирования приложения.

Рисунок 2.2 – Диаграмма компонентов ПО ТМСМ

Разработка основных функций сортировки данных

2.3 Разработка функции сортировки методом выбора

Сигнатура функции сортировки массива методом выбора приведена в листинге 2.1. Функция принимает исходный массив __array_ в качестве аргумента и возвращает уже отсортированный массив.

Листинг 2.1 – Сигнатура функции сортировки методом выбора

/// <summary>

/// Sort array by selections method

/// </summary>

/// <param name="__array_">Array to sort</param>

/// <returns>Array after sorting</returns>

/// <typeparam name="T">any type of array elements</typeparam>

public static T[] SelectionsSort<T>(T[] __array_) where T : IComparable<T>

Полный листинг функции сортировки массива методом выбора приведен в приложении А.

На рисунке 2.3 приведена блок-схема алгоритма сортировки массива методом выбора. Эта и следующие блок-схемы в данной работе выполнены с помощью программы MS Visio 2016.

Рисунок 2.3 – Блок-схема алгоритма сортировки методом выбора

2.4 Разработка функции сортировки методом обмена

Сигнатура функции сортировки массива методом обмена приведена в листинге 2.2. Функция принимает исходный массив __array_ в качестве аргумента и возвращает уже отсортированный массив.

Листинг 2.2 – Сигнатура функции сортировки методом обмена

/// <summary>

/// Sort array by bubbles method

/// </summary>

/// <param name="__array_">Array to sort</param>

/// <returns>Array after sorting</returns>

/// <typeparam name="T">any type of array elements</typeparam>

public static T[] BubbleSort<T>(T[] __array_) where T : IComparable<T>

Полный листинг функции сортировки массива методом обмена приведен в приложении Б.

На рисунке 2.4 приведена блок-схема алгоритма сортировки массива методом обмена.

Рисунок 2.4 – Блок-схема алгоритма сортировки методом обмена

2.5 Разработка функции сортировки методом вставок

Сигнатура функции сортировки массива методом вставок приведена в листинге 2.3. Функция принимает исходный массив __array_ в качестве аргумента и возвращает уже отсортированный массив.

Листинг 2.3 – Сигнатура функции сортировки методом вставок

/// <summary>

/// Sort array by insertions method

/// </summary>

/// <param name="__array_">Array to sort</param>

/// <returns>Array after sorting</returns>

/// <typeparam name="T">any type of array elements</typeparam>

public static T[] InsertionsSort<T>(T[] __array_) where T : IComparable<T>

Полный листинг функции сортировки массива методом вставок приведен в приложении В.

На рисунке 2.5 приведена блок-схема алгоритма сортировки массива методом вставок.

Рисунок 2.5 – Блок-схема алгоритма сортировки методом вставок

2.6 Разработка функции сортировки методом Шелла

Сигнатура функции сортировки массива методом Шелла приведена в листинге 2.4. Функция принимает исходный массив __array_ в качестве аргумента и возвращает уже отсортированный массив.

Листинг 2.4 – Сигнатура функции сортировки методом Шелла

/// <summary>

/// Sort array by Shell method

/// </summary>

/// <param name="__array_">Array to sort</param>

/// <returns>Array after sorting</returns>

/// <typeparam name="T">any type of array elements</typeparam>

public static T[] SortByShell<T>(T[] __array_) where T: IComparable<T>

Полный листинг функции сортировки массива методом Шелла приведен в приложении Г.

На рисунке 2.6 приведена блок-схема алгоритма сортировки массива методом Шелла.

Рисунок 2.6 – Блок-схема алгоритма сортировки методом Шелла

2.7 Разработка функции метода быстрой сортировки

Сигнатура функции метода быстрой сортировки массива приведена в листинге 2.5. Функция принимает исходный массив __array_ в качестве аргумента и возвращает уже отсортированный массив.

Листинг 2.5 – Сигнатура функции сортировки методом выбора

/// <summary>

/// Sort array by quick sort

/// </summary>

/// <param name="__array_">Array to sort</param>

/// <returns>Array after sorting</returns>

/// <typeparam name="T">any type of array elements</typeparam>

public static T[] QuickSort<T>(T[] __array_) where T : IComparable<T>

Метод быстрой сортировки использует рекурсивную процедуру – _quickSort сортировки подмассивов (левого и правого относительно выбранного опорного элемента). Функция __quickSort принимает исходный массив на текущей итерации сортировки и индексы левого и правого подмассивов. Общая сигнатура данной рекурсивной функции приведена в листинге 2.6.

Листинг 2.6 – Сигнатуры функций сортировки методом выбора

/// <summary>

/// Recurrent quick sort

/// </summary>

/// <typeparam name="T">any type of array elements</typeparam>

/// <param name="__array_">Part of array to sort on current step</param>

/// <param name="left"></param>

/// <param name="right"></param>

private static void _quickSort<T>(T[] __array_, int left, int right) where T : IComparable<T>

Полный листинг функции алгоритма метода быстрой сортировки приведен в приложении Д.

На рисунке 2.7 приведена блок-схема алгоритма метода быстрой сортировки массива – главной функции QuickSort и функции рекурсивной сортировки __quickSort.

Рисунок 2.7 – Блок-схема алгоритма методом быстрой сортировки

Описание интерфейса программы

Интерфейс ПО ТМСТ состоит из одного главного окна, на котором расположены (рисунок 2.8):

область выбора тестируемых методов сортировки;
область настройки параметров эксперимента типа 1 (исследование эффективности методов сортировки в зависимости от размера массива);
область настройки параметров эксперимента типа 2 (исследование эффективности методов сортировки в зависимости от исходной степени упорядоченности массива);
область вывода результатов эксперимента типа 1 в виде графических зависимостей;
область вывода результатов эксперимента типа 2 в виде графических зависимостей;

Рисунок 2.8 – Вид главного окна ПО ТМСМ

Вывод по главе 2

В ходе работы было разработано математическое и программное обеспечение, которое способно воспроизводить два типа экспериментов с целью исследования эффективности сортировки массивов данных:

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

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

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

с изменением размера сортируемой последовательности для различных степеней исходной упорядоченности;
с изменением степени исходной упорядоченности сортируемой последовательности для различного размера.

В ходе экспериментов будут определяться и строиться графики следующих параметров:

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

Исходная степень упорядоченности сортируемой последовательности будет задаваться в процентах от общего числа ее элементов. Для придания последовательности исходной степени упорядоченности будут выполняться следующие действия:

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

3. Проведение экспериментов по сортировке последовательности с изменением ее длины разными методами

Эксперимент с изменением размера сортируемой последовательности будет проводиться для диапазона значений длины массива от 1000 до 10000 элементов. Будет проведена серия из трех таких экспериментов для различных степеней исходной упорядоченности: 0% (абсолютно упорядоченный массив), 50% (частично упорядоченный массив), 100% (абсолютно неупорядоченный массив).

На рисунке 3.1 приведены результаты зависимости характеристик сортировки от размера абсолютно упорядоченного массива в диапазоне от 1000 до 1000 элементов.

Рисунок 3.1 – Результаты эксперимента сортировки абсолютно упорядоченного массива с изменением размера от 1000 до 10000 элементов

На рисунке 3.2 приведены результаты зависимости характеристик сортировки от размера частично упорядоченного массива в диапазоне от 1000 до 1000 элементов.

Рисунок 3.2 – Результаты эксперимента сортировки частично упорядоченного массива с изменением размера от 1000 до 10000 элементов

На рисунке 3.3 приведены результаты зависимости характеристик сортировки от размера абсолютно неупорядоченного массива в диапазоне от 1000 до 1000 элементов.

Рисунок 3.3 – Результаты эксперимента сортировки абсолютно неупорядоченного массива с изменением размера от 1000 до 10000 элементов

Проведение экспериментов по сортировке последовательности с изменением степени ее исходной упорядоченности разными методами

Эксперимент с изменением степени исходной упорядоченности сортируемой последовательности будет проводиться для диапазона от 0 (абсолютно упорядоченный) до 100 (абсолютно неупорядоченный) процентов. Будет проведено два таких экспериментов для различных размеров: 1000 и 10000 элементов.

На рисунке 3.4 приведены результаты эксперимента сортировки массива из 1000 элементов с изменением степени исходной упорядоченности от 0 до 100 процентов.

Рисунок 3.4 – Результаты эксперимента сортировки массива из 1000 элементов с изменением степени исходной упорядоченности от 0% до 100%

На рисунке 3.5 приведены результаты эксперимента сортировки массива из 10000 элементов с изменением степени исходной упорядоченности от 0 до 100 процентов.

Рисунок 3.5 – Результаты эксперимента сортировки массива из 10000 элементов с изменением степени исходной упорядоченности от 0% до 100%

Вывод по главе 3

Результаты проведенных экспериментов (3.1 – 3.5) показали, что:

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

Заключение

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

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

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

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

В результате выполнения работы были решены следующие задачи:

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

Список использованных источников

Асхабов Х. И. Алгоритмы сортировки неупорядоченных статических массивов и их реализация в Lazarus. КНИИ РАН, г. Грозный, Россия. Грозненский естественнонаучный бюллетень, том 3, №5 (13), 2018, 10 с.
Ахо А. В., Хопкрофт Д. Э., Ульман Д. Д.Структуры данных и алгоритмы = Data structures and algorithms / Под ред. А. А. Минько. — М.: Вильямс, 2000. — 382 с.
Вершинин М., Иванова Е. C# Enterprise Edition. Технологии проектирования и разработки. – М.: BHV, 2003 г. – 1088 с.
Вирт Н. Алгоритмы и структуры данных = Algoritms and data structure. — М.: Мир, 1989. — 360 с.
Воройский Ф. С. Информатика. Новый систематизированный толковый словарь-справочник. — 3-е изд.. — М.: ФИЗМАТЛИТ, 2003. — 760 с. — (Введение в современные информационные и телекоммуникационные технологии в терминах и фактах).
Громов Ю.Ю. – Технология программирования: учебное пособие / Ю.Ю. Громов, О.Г. Иванова, М.П. Беляев, Ю.В. Минин. – Тамбов: Изд-во ФГБОУ ВПО «ТГТУ», 2013. – 172 с.
Джозеф Албахари – C#. Справочник. Полное описание языка. Пер. с англ. - М: ООО «И.Д. Вильямс», 6-е изд., 2016, 1040 с.
Дональд Кнут. Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. 2 - е изд. М. : «Вильямс», 2008. 824 с.
Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2013. – 1277 с.
Королевство Дельфи. Виртуальный клуб программистов. URL: http: //delphikingdom.com (дата обращения: 02.02.2019).
Левитин А. В. Алгоритмы. Введение в разработку и анализ — М.: Вильямс, 2016. — 576 с.
Макоха А.Н Компьютерные науки. Введение в язык программирования Турбо Паскаль: В 3 ч. Ч. III.: Учебное пособие. – Ставрополь: Изд-во СГУ, 2001.
Роберт Седжвик. Фундаментальные алгоритмы на C++. Анализ/Структуры данных/Сортировка/Поиск — СПб.: ДиаСофтЮП, 2003. – 687 с.
Тюгашев А.А. Основы программирования. Часть I. – СПб: Университет ИТМО, 2016. – 160 с.
Фаронов В.В. Delphi. Программирование на языке высокого уровня: учебник для вузов. СПб., Питер. 2007. 639 с.

Приложение А. Исходный код алгоритма сортировки методом выбора, записанный на языке программирования C#

/// <summary>

/// Sort array by selections method

/// </summary>

/// <param name="__array_">Array to sort</param>

/// <returns>Array after sorting</returns>

/// <typeparam name="T">any type of array elements</typeparam>

public static T[] SelectionsSort<T>(T[] __array_) where T : IComparable<T>

{

//------------------------------------------

// reset sorting analytics to initial values

//------------------------------------------

OperationsCount = 0;

Duration = 0;

System.Diagnostics.Stopwatch SortTimer = new System.Diagnostics.Stopwatch();

SortTimer.Start();

//------------------------------------------

// temporary value for exchanging

T temp, currentSmallest;

// temporary values

int sortedRangeEnd = 0, currentSmallestIndex = 0;

// temporary array to return

T[] __array = new T[__array_.GetLength(0)];

// copy array

for (int i = 0; i < __array_.GetLength(0); i++)

__array[i] = __array_[i];

// sorting

while (sortedRangeEnd < __array.GetLength(0))

{

// find index of smallest from index

currentSmallest = __array[sortedRangeEnd];

currentSmallestIndex = sortedRangeEnd;

for (int i = sortedRangeEnd + 1; i < __array.GetLength(0); i++)

{

/* operations++ */ OperationsCount++;

if (currentSmallest.CompareTo(__array[i]) > 0)

{

currentSmallest = __array[i];

currentSmallestIndex = i;

/* operations++ */ OperationsCount++;

}

// swap elements

temp = __array[sortedRangeEnd];

__array[sortedRangeEnd] = __array[currentSmallestIndex];

__array[currentSmallestIndex] = temp;

/* operations++ */ OperationsCount += 3;

// continue

sortedRangeEnd++;

}

//------------------------------------------

// stop sorting time

SortTimer.Stop();

Duration = SortTimer.ElapsedMilliseconds;

//------------------------------------------

// return result

return __array;

}

Приложение Б. Исходный код алгоритма сортировки методом обмена, записанный на языке программирования C#

/// <summary>

/// Sort array by bubbles method

/// </summary>

/// <param name="__array_">Array to sort</param>

/// <returns>Array after sorting</returns>

/// <typeparam name="T">any type of array elements</typeparam>

public static T[] BubbleSort<T>(T[] __array_) where T : IComparable<T>

{

//------------------------------------------

// reset sorting analytics to initial values

//------------------------------------------

OperationsCount = 0;

Duration = 0;

System.Diagnostics.Stopwatch SortTimer = new System.Diagnostics.Stopwatch();

SortTimer.Start();

//------------------------------------------

// temporary swapping flag

bool swapped;

// temporary value for exchanging

T temp;

// temporary array to return

T[] __array = new T[__array_.GetLength(0)];

// copy array

for (int i = 0; i < __array_.GetLength(0); i++)

__array[i] = __array_[i];

// sorting

{

swapped = false;

for (int i = 1; i < __array.GetLength(0); i++)

{

/* operations++ */ OperationsCount++;

if (__array[i - 1].CompareTo(__array[i]) > 0)

{

temp = __array[i - 1];

__array[i - 1] = __array[i];

__array[i] = temp;

swapped = true;

/* operations++ */ OperationsCount += 3;

}

} while (swapped != false);

//------------------------------------------

// stop sorting time

SortTimer.Stop();

Duration = SortTimer.ElapsedMilliseconds;

//------------------------------------------

// return result

return __array;

}

Приложение В. Исходный код алгоритма сортировки методом вставок, записанный на языке программирования C#

/// <summary>

/// Sort array by insertions method

/// </summary>

/// <param name="__array_">Array to sort</param>

/// <returns>Array after sorting</returns>

/// <typeparam name="T">any type of array elements</typeparam>

public static T[] InsertionsSort<T>(T[] __array_) where T : IComparable<T>

{

//------------------------------------------

// reset sorting analytics to initial values

//------------------------------------------

OperationsCount = 0;

Duration = 0;

System.Diagnostics.Stopwatch SortTimer = new System.Diagnostics.Stopwatch();

SortTimer.Start();

//------------------------------------------

// temporary value for exchanging

T temp;

// temporary values

int sortedRangeEndIndex = 1, ins_index = 0;

// temporary array to return

T[] __array = new T[__array_.GetLength(0)];

// copy array

for (int i = 0; i < __array_.GetLength(0); i++) __array[i] = __array_[i];

// sorting

while (sortedRangeEndIndex < __array.GetLength(0))

{

/* operations++ */ OperationsCount++;

if (__array[sortedRangeEndIndex].CompareTo(__array[sortedRangeEndIndex-1])<0)

{

// find index to insert

for (int index = 0; index < __array.GetLength(0); index++)

{

/* operations++ */ OperationsCount++;

if (__array[index].CompareTo(__array[sortedRangeEndIndex]) > 0)

{

ins_index = index; break;

}

} // insert

temp = __array[ins_index];

__array[ins_index] = __array[sortedRangeEndIndex];

for (int current = sortedRangeEndIndex; current>ins_index; current--)

{

/* operations++ */ OperationsCount++;

__array[current] = __array[current - 1];

}

__array[ins_index + 1] = temp;

/* operations++ */ OperationsCount += 3;

}

// next position

sortedRangeEndIndex++;

/* operations++ */ OperationsCount++;

}

//------------------------------------------

// stop sorting time

SortTimer.Stop();

Duration = SortTimer.ElapsedMilliseconds;

//------------------------------------------

// return result

return __array;

}

Приложение Г. Исходный код алгоритма сортировки методом Шелла, записанный на языке программирования C#

/// <summary>

/// Sort array by Shell method

/// </summary>

/// <param name="__array_">Array to sort</param>

/// <returns>Array after sorting</returns>

/// <typeparam name="T">any type of array elements</typeparam>

public static T[] SortByShell<T>(T[] __array_) where T: IComparable<T>

{

//------------------------------------------

// reset sorting analytics to initial values

//------------------------------------------

OperationsCount = 0;

Duration = 0;

System.Diagnostics.Stopwatch SortTimer = new System.Diagnostics.Stopwatch();

SortTimer.Start();

//------------------------------------------

// temporary value for exchanging

T temp;

// counters

int i, j, k;

// temporary array to return

T[] __array = new T[__array_.GetLength(0)];

// copy array

for (i = 0; i < __array_.GetLength(0); i++)

__array[i] = __array_[i];

// sorting

for (k = __array.GetLength(0) / 2; k > 0; k /= 2)

for (i = k; i < __array.GetLength(0); i++)

{

temp = __array[i];

/* operations++ */ OperationsCount++;

for (j = i; j >= k; j -= k)

{

/* operations++ */ OperationsCount++;

if (temp.CompareTo(__array[j - k]) < 0)

{

__array[j] = __array[j - k];

/* operations++ */ OperationsCount++;

}

else

break;

}

__array[j] = temp;

/* operations++ */ OperationsCount++;

}

//------------------------------------------

// stop sorting time

SortTimer.Stop();

Duration = SortTimer.ElapsedMilliseconds;

//------------------------------------------

// return result

return __array;

}

Приложение Д. Исходный код алгоритма методом быстрой сортировки, записанный на языке программирования C#

/// <summary>

/// Sort array by quick sort

/// </summary>

/// <param name="__array_">Array to sort</param>

/// <returns>Array after sorting</returns>

/// <typeparam name="T">any type of array elements</typeparam>

public static T[] QuickSort<T>(T[] __array_) where T : IComparable<T>

{

//------------------------------------------

// reset sorting analytics to initial values

//------------------------------------------

OperationsCount = 0;

Duration = 0;

System.Diagnostics.Stopwatch SortTimer = new System.Diagnostics.Stopwatch();

SortTimer.Start();

//------------------------------------------

// temporary array to return

T[] __array = new T[__array_.GetLength(0)];

// copy array

for (int i = 0; i < __array_.GetLength(0); i++)

__array[i] = __array_[i];

// sorting

_quickSort(__array, 0, __array.GetLength(0) - 1);

//------------------------------------------

// stop sorting time

SortTimer.Stop();

Duration = SortTimer.ElapsedMilliseconds;

//------------------------------------------

// return result

return __array;

}

/// <summary>

/// Recurrent quick sort

/// </summary>

/// <typeparam name="T">any type of array elements</typeparam>

/// <param name="__array_">Part of array to sort on current step</param>

/// <param name="left"></param>

/// <param name="right"></param>

private static void _quickSort<T>(T[] __array_, int left, int right) where T : IComparable<T>

{

// temporary value for exchanging

T temp;

// if need to sort

/* operations++ */ OperationsCount++;

if (left < right)

{

// temporary values

int pivotIndex = _pivotRng.Next(left, right);

T pivotValue = __array_[pivotIndex];

int storeIndex = left;

/* operations++ */ OperationsCount++;

// swap elements

temp = __array_[pivotIndex];

__array_[pivotIndex] = __array_[right];

__array_[right] = temp;

/* operations++ */ OperationsCount += 3;

for (int i = left; i < right; i++)

{

/* operations++ */ OperationsCount++;

if (__array_[i].CompareTo(pivotValue) < 0)

{

// swap elements

temp = __array_[i];

__array_[i] = __array_[storeIndex];

__array_[storeIndex] = temp;

storeIndex += 1;

/* operations++ */ OperationsCount += 3;

}

// swap elements

temp = __array_[storeIndex];

__array_[storeIndex] = __array_[right];

__array_[right] = temp;

/* operations++ */ OperationsCount += 3;

// recurrent sorting

_quickSort(__array_, left, storeIndex - 1);

_quickSort(__array_, storeIndex + 1, right);

}