Исследование эффективности алгоритмов сортировок для различных структур и размерностей данных

Постановка задачи

• · Провести экспериментальный сравнительный анализ различных методов сортировки. Для чистоты эксперимента сортировка должна проводиться на одинаковых наборах входных данных, которые генерируются случайным образом. Для более полного анализа методов сортировка должна проводиться для различных размерностей данных, например: 500, 1000, 3000, 5000, 8000, 10 000, 30 000, 60 000.
• · Исходные наборы данных — массивы или файлы соответствующего типа (по № варианта).
• · Проследить динамику роста требуемого для сортировки времени.
• · Проверить, как ведут себя методы на различных входных данных: упорядоченных в прямом порядке, упорядоченных в обратном порядке и случайных.
• · Сравнить теоретические оценки времени сортировки и числа требуемых операций с экспериментальными.
• · Построить соответствующие таблицы и графики сравнительного анализа различных методов сортировки (по времени, размерности и исходной упорядоченности)
• · Провести исследования o для выбранных алгоритмов внутренней сортировки (один из методов вставки и один из методов обменной сортировки)

Теоретические положения.

Сортировка — это процесс упорядочения некоторого множества элементов, на котором определены отношения порядка >, <, ?, ?.

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

Алгоритмы сортировки оцениваются по скорости выполнения и эффективности использования памяти:

• · Время — характеризует быстродействие алгоритма. Эквивалентно вычислительной сложности. Для типичного алгоритма средняя сложность — O (n log n) и высокая — O (n2). Идеальное поведение для упорядочения — O (n).
• · Память —временное хранение данных. Обычно эти алгоритмы требуют O (log n) памяти. Алгоритмы сортировки, которые не потребляют дополнительной памяти, относят к сортировкам на месте.

Сортировка выбором

Самый простой алгоритм сортировок — это сортировка выбором. Судя по названию сортировки, необходимо что-то выбирать (максимальный или минимальный элементы массива). Алгоритм сортировки выбором находит в исходном массиве максимальный или минимальный элементы, в зависимости от того как необходимо сортировать массив, по возрастанию или по убыванию. Если массив должен быть отсортирован по возрастанию, то из исходного массива необходимо выбирать минимальные элементы. Если же массив необходимо отсортировать по убыванию, то выбирать следует максимальные элементы.

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

Сортировка простыми обменами, сортировка пузырьком

Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма: O (nІ).

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

Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим наибольшим элементом, а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма).

Гномья сортировка

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

Алгоритм концептуально простой, не требует вложенных циклов. Время работы. На практике алгоритм может работать так же быстро, как и сортировка вставками.

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

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

Сортировка вставками

Сортировка вставками — достаточно простой алгоритм. Массив делится на 2 части: отсортированную и неотсортированную. На каждом шаге берется очередной элемент из неотсортированной части и включается в отсортированную. Имеет высокую вычислительную сложность O (nІ). Отсортировано начало массива A1, A2, …, Ai-1. Остаток массива Ai,…An не отсортирован. На очередном шаге Ai включается в отсортированную часть на соответствующее место. Пример такой сортировки — сортировка с помощью двоичного дерева.

Сортировка слиянием

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

Блочная сортировка

Блочная сортировка (Карманная сортировка, корзинная сортировка, англ. Bucket sort) —алгоритм сортировки, в котором сортируемые элементы распределяются между конечным числом отдельных блоков (карманов, корзин) так, чтобы все элементы в каждом следующем по порядку блоке были всегда больше (или меньше), чем в предыдущем. Каждый блок затем сортируется отдельно, либо рекурсивно тем же методом, либо другим. Затем элементы помещаются обратно в массив. Этот тип сортировки может обладать линейным временем исполнения.

Преимущества: относится к классу быстрых алгоритмов с линейным временем исполнения O (N) (на удачных входных данных).

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

Сортировка Шелла.

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

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

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

Быстрая сортировка

Быстрая сортировка использует стратегию «разделяй и властвуй». Шаги алгоритма таковы:

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

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

Пирамидальная сортировка

Пирамида — двоичное дерево, в котором значение каждого элемента больше либо равно значений дочерних элементов.

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

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

Stooge Sort

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

• o Если значение элемента в конце списка меньше, чем значение элемента в начале, то поменять их местами.
• o Если есть 3 или более элементов в текущем подмножестве списка, то:
  • · Рекурсивно вызвать Stooge sort для первых 2/3 списка
  • · Рекурсивно вызвать Stooge sort для последних 2/3 списка
  • · Рекурсивно вызвать Stooge sort для первых 2/3 списка снова
• o Иначе: return

Результаты работы программы

· В этой части работы происходит сортировка 500, 1000, 2000, 3000, 5000 элементов различными видами сортировки.

Рис. 4. Пример работы 3-ей части программы

Таблица 2. Зависимость времени выполнения сортировки от количества элементов.

Рис. 5. Зависимость времени выполнения сортировки от количества элементов