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

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

Оценка временной сложности алгоритма сортировки методом обмена составляет 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 – фактическое время выполнения эксперимента в миллисекундах.