АНАЛИЗ ВРЕМЕННОЙ СЛОЖНОСТИ РЕКУРСИВНЫХ АЛГОРИТМОВ СОРТИРОВКИ QUICK SORT И MERGE SORT

​АННОТАЦИЯ

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

Ключевые слова: теория алгоритмов, анализ алгоритмов, сортировки, временная сложность, quick sort, merge sort.

В работе выполнено сравнение рекурсивных алгоритмов сортировки Quick Sort с одним указателем и Merge Sort, код выполнен на языке программирования С#. В код встроен счетчик tr cравнения и перестановки элементов.

Quick Sort — это рекурсивный алгоритм сортировки, который делит исходный массив на две части относительно опорного элемента, выбранного по определённому критерию (в нашем случае первый элемент массива). Все элементы, меньшие или равные опорному, перемещаются в одну часть массива, а все элементы, большие опорного, — в другую. Этот процесс разделения продолжается рекурсивно для каждой из получившихся частей массива, при этом на каждом этапе сортировка проводится только внутри текущей части относительно нового опорного элемента. Рекурсия продолжается до тех пор, пока каждая из частей не станет состоять из одного элемента или не окажется пустой, что соответствует выполнению условия выхода из рекурсии. После этого все части массива считаются отсортированными [1, c. 111].

Merge Sort — это рекурсивный алгоритм сортировки, который на каждом шаге рекурсии делит исходный массив на две примерно равные части, продолжая этот процесс до тех пор, пока каждая из частей не станет состоять из одного элемента. После завершения этапа разбиения начинается процесс обратной сборки, в ходе которого пары соседних частей объединяются в правильном порядке. Объединение выполняется с помощью сравнения элементов двух частей: выбирается меньший элемент из начальных элементов двух частей, и он добавляется в итоговый массив, после чего сравнение продолжается с оставшимися элементами, пока одна из частей не будет полностью исчерпана. Затем оставшиеся элементы из другой части добавляются в конец итогового массива. Этот процесс объединения повторяется на каждом уровне рекурсии, пока все части не будут соединены в один упорядоченный массив. Код исследуемых рекурсивных алгоритмов сортировки представлен на рисунках 1, 2, 3 и 4.

Рисунок 1. Код рекурсивного алгоритма сортировки Merge Sort

Рисунок 2. Продолжение кода рекурсивного алгоритма сортировки Merge Sort

Рисунок 3. Код рекурсивного алгоритма сортировки Quick Sort

Рисунок 4. Продолжение кода рекурсивного алгоритма сортировки Quick Sort

С целью акцентирования внимания на важных группах данных были взяты массивы размерами , где k принимает значение от 0 до 30, и значение округляем в большую сторону по следующим правилам:

Так как временная сложность алгоритма Merge Sort не зависит от расположения элементов, то и значения временной сложности для одинаковых по размеру массивов будут равны. В случае с алгоритмом Quick Sort временная сложность при одинаковых размерах массива может отличаться, поэтому для массива размера n считалось ее среднее арифметическое значение, полученное при выполнении программы 10 раз. Результаты, полученные в ходе выполнения программы представлены в таблице 1.

Таблица 1.

Результаты выполнения программ

Использовав метод наименьших квадратов, была получена аппроксимирующая функция. Функция была приведена к виду . Из определения метода:

                                                                               (1)

                                                             (2)

                                                            (3)

                                                         (4)

                                    (5)

                                            (6)

При  

                                                                          (7)

                                                                   (8)

                                                                                         (9)

 — коэффициент пропорциональности;

 — размер массива;

 — временная сложность.

Применив формулу (9), получаем функциональные зависимости в явном виде:

       (Merge Sort)

      (Quick Sort)

На графиках 1 и 2 изображено рассеяние точек для Merge Sort и Quick Sort соответственно. На графике 1 видно, что аппроксимирующая кривая хорошо ложится на точки рассеяния, а на графике 2 не отражает действительный тренд функции.

График 1. График рассеяния для алгоритма Merge Sort с проведенной аппроксимирующей кривой

График 2. Рассеяние точек для алгоритма Quick Sort с проведенной аппроксимирующей кривой

Была проведена аппроксимация к квадратичной функции. Результатом приведения к квадратичной зависимости вида:  является полином с коэффициентами

0     

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

График 3. Рассеяние точек для алгоритма Quick Sort с проведенной аппроксимирующей кривой

Для Merge Sort результат весьма предсказуем, что не сказать про Quick Sort, где в зависимости от начального массива, временная сложность варьируется от  до , при значениях размера массива от 1 до 30 000, хорошо описывается как  и после 30 000 плавно перетекает в .

Для визуализации сравнения алгоритмов, на одну координатную сетку были нанесены две аппроксимирующие кривые, что представлено на графике 4, нижней (синей) линией представлен Merge Sort, верхней (оранжевой) Quick Sort. На графике видно, что при размерах массива, меньших 30 000, аппроксимирующие прямые практически сливаются, и дальше Quick Sort уступает Merge Sort.

График 4. Сравнение аппроксимирующих прямым временной сложности для алгоритмов Quick Sort и Merge Sort

Емкостная сложность алгоритмов Quick Sort и Merge Sort

Quick Sort

Емкостная сложность зависит от глубины рекурсии, а также от дополнительных данных, которые могут быть использованы для разделения массива. Лучший и средний случай (когда разделение массива происходит сбалансированно). Для каждого рекурсивного вызова алгоритм разделяет массив на два подмассива. В лучшем случае рекурсия зайдет в глубину  уровней, где n — размер массива. Однако, из-за использования стека вызовов, каждый рекурсивный вызов занимает некоторое место в памяти. В среднем (при сбалансированном разделении) глубина рекурсии будет так же порядка . Алгоритм работает на месте (in-place), т.е. не использует дополнительную память для хранения данных, кроме временных переменных. Худший случай (например, когда массив уже отсортирован или отсортирован в обратном порядке). Если разделение массива на подмассивы будет неравномерным (например, каждый раз разделяется только один элемент), глубина рекурсии может увеличиться до . Тогда память для стека вызовов:

Merge Sort

Алгоритм Merge Sort всегда делит массив пополам до тех пор, пока не останутся одноэлементные подмассивы, а затем сливает их обратно в отсортированном порядке. Merge Sort также использует рекурсию, но в отличие от Quick Sort, требует дополнительной памяти для хранения промежуточных массивов при слиянии. Сложность слияния на каждом уровне рекурсии — O(n), так как для слияния всех элементов в массивах потребуется временное место. Глубина рекурсии —  так как на каждом уровне массив делится пополам. Для слияния используется дополнительная память, пропорциональная размеру массива n. Это требует  памяти на каждом уровне рекурсии.

Merge Sort всегда требует больше памяти, чем Quick Sort, из-за необходимости дополнительной памяти для слияния массивов.

Quick Sort в среднем работает с меньшими требованиями к памяти, но может потребовать большего объема памяти в худшем случае (если разделение массива не сбалансированно).

Временная сложность быстрой сортировки, полученная аналитически.

Пусть T(n) — время выполнения быстрой сортировки для массива длины n. В лучшем случае, массив делится на две примерно равные части. Тогда:

Здесь O(n) — это время, необходимое для разделения массива.

Применяя мастер-теорему [2] к этому уравнению, получаем:

Таким образом, временная сложность в среднем и лучшем случаях равна

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

Итак, временная сложность быстрой сортировки:

Лучший и средний случаи:

Худший случай:

Временная сложность сортировки слиянием

Пусть T(n) — время выполнения сортировки слиянием для массива длины n. Сначала массив делится на две части, что дает два подмассива длины , а объединение требует O(n) операций.

Применив мастер-теорему:

Худший случай: поскольку алгоритм всегда делит массив пополам и объединяет его за линейное время, его худший случай также равен

Итак, временная сложность сортировки

Выводы

Производительность Quick Sort с одним указателем показывает лучшие значения при размерах массива меньших 30 000, за счет практически одинаковой временной сложности с Merge Sort, но меньшими требованиями к памяти. Merge Sort может быть менее эффективен при малых размеров массива из-за необходимости дополнительной памяти для временных массивов, но его производительность более предсказуема. При больших входах Merge Sort является более производительным и более стабильным, чем Quick Sort с одним указателем.

Quick Sort с одним указателем использует  дополнительной памяти для хранения стека вызовов при рекурсивных вызовах, что делает его более экономичным в использовании памяти. Merge Sort требует O(n) дополнительной памяти, так как для выполнения сортировки создаются временные массивы для слияния.

Применение Quick Sort с одним указателем рационально при сортировке массивов с числом элементов меньших 30 000. Merge Sort стоит использовать для сортировки связанных списков и в системах, где важна стабильность и предсказуемость времени выполнения, он стабильнее Quick Sort при сортировке больших массивов.

Список литературы:

1. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. – 3 издание, MIT Press, 2009.
2. Algorithmica.org. Мастер-теорема // [электронный ресурс]. — Режим доступа. — URL: https://ru.algorithmica.org/cs/complexity/master-theorem/ (дата обращения 25.11.2024).