Какую временную сложность имеет алгоритм сортировки слиянием

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

Сортировка слиянием (англ. Merge sort) — алгоритм сортировки, использующий [math]O(n)[/math] дополнительной памяти и работающий за [math]O(n\log(n))[/math] времени.

Принцип работы

Пример работы процедуры слияния.

Пример работы рекурсивного алгоритма сортировки слиянием

Пример работы итеративного алгоритма сортировки слиянием

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

1. Если в рассматриваемом массиве один элемент, то он уже отсортирован — алгоритм завершает работу.
2. Иначе массив разбивается на две части, которые сортируются рекурсивно.
3. После сортировки двух частей массива к ним применяется процедура слияния, которая по двум отсортированным частям получает исходный отсортированный массив.

Слияние двух массивов

У нас есть два массива [math]a[/math] и [math]b[/math] (фактически это будут две части одного массива, но для удобства будем писать, что у нас просто два массива). Нам надо получить массив [math]c[/math] размером [math]|a| + |b|[/math] . Для этого можно применить процедуру слияния. Эта процедура заключается в том, что мы сравниваем элементы массивов (начиная с начала) и меньший из них записываем в финальный. И затем, в массиве у которого оказался меньший элемент, переходим к следующему элементу и сравниваем теперь его. В конце, если один из массивов закончился, мы просто дописываем в финальный другой массив. После мы наш финальный массив записываем заместо двух исходных и получаем отсортированный участок.

Множество отсортированных списков с операцией [math]\mathrm[/math] является моноидом, где нейтральным элементом будет пустой список.

Ниже приведён псевдокод процедуры слияния, который сливает две части массива [math]a[/math] — [math][left; mid)[/math] и [math][mid; right)[/math]

function merge(a : int[n]; left, mid, right : int): it1 = 0 it2 = 0 result : int[right - left] while left + it1 < mid and mid + it2 < right if a[left + it1] < a[mid + it2] result[it1 + it2] = a[left + it1] it1 += 1 else result[it1 + it2] = a[mid + it2] it2 += 1 while left + it1 < mid result[it1 + it2] = a[left + it1] it1 += 1 while mid + it2 < right result[it1 + it2] = a[mid + it2] it2 += 1 for i = 0 to it1 + it2 a[left + i] = result[i]

Рекурсивный алгоритм

Функция сортирует подотрезок массива с индексами в полуинтервале [math][left; right)[/math] .

function mergeSortRecursive(a : int[n]; left, right : int): if left + 1 >= right return mid = (left + right) / 2 mergeSortRecursive(a, left, mid) mergeSortRecursive(a, mid, right) merge(a, left, mid, right)

Итеративный алгоритм

При итеративном алгоритме используется на [math]O(\log n)[/math] меньше памяти, которая раньше тратилась на рекурсивные вызовы.

function mergeSortIterative(a : int[n]): for i = 1 to n, i *= 2 for j = 0 to n - i, j += 2 * i merge(a, j, j + i, min(j + 2 * i, n))

Время работы

Чтобы оценить время работы этого алгоритма, составим рекуррентное соотношение. Пускай [math]T(n)[/math] — время сортировки массива длины [math]n[/math] , тогда для сортировки слиянием справедливо [math]T(n)=2T(n/2)+O(n)[/math]
[math]O(n)[/math] — время, необходимое на то, чтобы слить два массива длины [math]n[/math] . Распишем это соотношение:

Сравнение с другими алгоритмами

• устойчивая,
• можно написать эффективную многопоточную сортировку слиянием,
• сортировка данных, расположенных на периферийных устройствах и не вмещающихся в оперативную память [1] .

• требуется дополнительно [math]O(n)[/math] памяти, но можно модифицировать до [math]O(1)[/math] .

См. также

• Сортировка кучей
• Быстрая сортировка
• Timsort
• Cортировка слиянием с использованием O(1) дополнительной памяти

Примечания

Худшее, среднее и лучшее время работы алгоритма

Когда мы говорим, что время работы алгоритма равно $$T(n)$$, мы имеем в виду, что $$T(n)$$ является верхней границей времени выполнения, то есть имеет место для всех входных данных размера $$n$$. Это называется анализом наихудшего случая. Алгоритм может работать значительно быстрее на некоторых размерах входных данных $$n$$, но это не имеет значения при оценке худшего случая. Если на выполнение алгоритма требуется $$T(n) = cn^2+k$$ шагов хотя бы для одного входного значения $$n$$ и $$T(n) = cn+k$$ шагов на всех остальных входных данных, мы все равно говорим, что алгоритм является квадратным, то есть в худшем случае работает за время пропорциональное $$n^2$$. Нужно понимать, что знание сложности алгоритма в худшем случае является очень важным, так как имеет решающее значение в возможности применения данного алгорит

Популярная альтернатива анализу наихудшего случая — анализ среднего случая. Здесь мы не пытаемся найти худший случай времени выполнения, а попытаться вычислить ожидаемое время, затраченное на случайно выбранных входных данных. Такой анализ, как правило, сложнее, так как он включает в себя вероятностные рассуждения и часто требует знания о распределении входных данных. С другой стороны, он может быть более полезным, потому что иногда наихудший случай алгоритма является обманчиво плохим. Хорошим примером этого, является популярный алгоритм быстрой сортировки, время работы которого в худшем случае на массиве длины $$n$$ пропорциональное $$n^2$$, однако ожидаемое в среднем время работы пропорциональное $$n\log n$$.

Намного меньше информации об алгоритме может сказать оценка наилучшего случая.

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

int LinearSearch(int[] arr, int x) < for (int i = 0; i < a.Length; i++) < if (arr[i] == x) return i; > return -1; > 

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

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

Средний случай

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

Лучший случай

При анализе сложности алгоритма в лучшем случае, мы вычисляем нижнюю границу времени работы алгоритма. Мы должны знать случай, на котором выполянется минимальное количество операций. В случае с линейным поиском, лучший случаем является поиск самого первого элемента в массиве. В таком случае количество затраченных операций будет всегда константным, то есть не будет зависеть от размера входного массива. Таким образом, сложность алгоритма линейного поиска в лучшем случае равна $$\Theta (1)$$.

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

Для некоторых алгоритмов все три случая сложности совпадают. Например, сортировка слиянием в лучшем, среднем и худшем случае имеет сложность $$\Theta (n \log n)$$. Однако один из самых быстрых алгоритмов сортировки на практике — быстрая сортировка, имеет в худшем случае (массив уже отсортирован) квадратичную сложность работы, при выборе разделяющего элемента последним в массиве. Для сортировки вставками, наихудший случай достигается когда массив отсортирован в обратном порядке, а наилучший когда массив уже отсортирован в нужном порядке.

results matching » «

No results matching » «

Сортировки

Сортировкой (англ. sorting) называется процесс упорядочивания множества объектов по какому-либо признаку.

Так как данные могут хранится в разных структурах, то и алгоритмы для каждой структуры могут отличаться. Например, при хранении данных в списке сортировка кучей потребует $O(n^2 \log n)$ времени против $O(n \log n)$ с использованием массива; а вот сортировка пузырьком не изменится.

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

Классификация сортировок

Время работы

Эту классификацию обычно считают самой важной. Оценивают худшее время алгоритма, среднее и лучшее. Лучшее время — минимальное время работы алгоритма на каком-либо наборе, обычно этим набором является тривиальный $\big[ 1 \ldots n \big] $. Худшее время — наибольшее время. У большинства алгоритмов временные оценки бывают $O(n \log n)$ и $O(n^2)$.

Память

Параметр сортировки, показывающий, сколько дополнительной памяти требуется алгоритму. Сюда входят и дополнительный массив, и переменные, и затраты на стек вызовов. Обычно затраты бывают $O(1)$, $O(\log n)$, $O(n)$.

Устойчивость

Устойчивой сортировкой называется сортировка, не меняющая порядка объектов с одинаковыми ключами. Ключ — поле элемента, по которому мы производим сортировку.

Количество обменов

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

Детерминированность

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

Сравнение сортировок

Рассмотрим массив $\big[ 1 \ldots n \big]$. Для элементов должно выполняться отношение порядка.

Название	Лучшее время	Среднее	Худшее	Память	Устойчивость	Обмены (в среднем)	Описание
Сортировка пузырьком (Bubble Sort)	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	Да	$O(n^2)$	Алгоритм состоит в повторяющихся проходах по сортируемому массиву. На каждой итерации последовательно сравниваются соседние элементы, и, если порядок в паре неверный, то элементы меняют местами.
Сортировка вставками (Insertion Sort)	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	Да	$O(n^2)$	На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированной части массива до тех пор, пока весь набор входных данных не будет отсортирован.
Сортировка Шелла (Shellsort)	$O(n\log^2)$	Зависит от выбора шага	$O(n^2)$	$O(1)$	Нет	$O(n^2)$	Является модификацией сортировки вставками, сортируем между собой элементы, стоящие на кратных нашему шагу местах.
Сортировка выбором (Selection Sort)	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	Нет	$O(n)$	На $i$-ом шаге алгоритма находим минимальный среди последних $n — i + 1$, и меняем его местами с $i$-ым элементом в массиве.
Быстрая сортировка (Quick Sort)	$O(n \log n)$	$O(n \log n)$	$O(n^2)$ (маловероятно)	$O(\log n)$ (стек вызовов)	Нет	$O(n \log n)$	Один из самых известных и широко используемых алгоритмов сортировки. Алгоритм состоит в выборе опорного элемента, разделении массива на 2 части относительно опорного (одна — все элементы, меньшие опорного элемента, вторая — большие), и в сортировке полученных частей рекурсивным вызовом себя от них.
Сортировка слиянием (Merge Sort)	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	$O(n)$ (обычная реализация) $O(1)$ (модифицированная реализация)	Да	$O(n \log n)$	Алгоритм состоит в разделении массива пополам, сортировке половин и их слиянии.
Timsort	$O(n)$	$O(n\log)$	$O(n\log)$	$O(n)$	Да	$O(n\log)$	Гибрид сортировки слиянием. Разбиваем массив на подмассивы фиксированной длины и сортируем каждый подмассив любой устойчивой сортировкой. После чего объединяем отсортированные подмассивы модифицированной сортировкой слиянием.
Сортировка кучей (Heap Sort)	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	$O(1)$	Нет	$O(n \log n)$	Строим из массива кучу, по очереди извлекаем минимум кучи.
Плавная сортировка (Smoothsort)	$O(n)$	$O(n\log)$	$O(n\log)$	$O(1)$	Нет	$O(n\log)$	Модификация сортировки кучей. Вместо двоичной кучи используем K-ую кучу Леонардо.
Терпеливая сортировка (Patience sorting)	$O(n\log)$	$O(n\log)$	$O(n\log)$	$O(n)$	Нет	$O(n\log)$	Раскидываем элементы массива по стопкам, после чего строим двоичную кучу из стопок. Позволяет также вычислить длину наибольшей возрастающей подпоследовательности данного массива.
Сортировка с помощью бинарного дерева (Tree Sort)	$O(n)$	$O(n \log n)$	$O(n \log n)$	$O(n)$	Да	$O(n)$	Добавляем по очереди вершины в сбалансированное дерево поиска, проходим по всем вершинам в порядке возрастания.
Карманная сортировка (Bucket Sort)	$O(n + k)$	$O(n \log_k n)$	$O(n \cdot k)$	$O(n)$	Да	—	Распределяем элементы в $k$ карманов, сортируем элементы внутри карманов, из каждого кармана данные записываются в массив в порядке разбиения.
Цифровая сортировка (Radix Sort)	$O(n \lg n)$	$O(n \lg n)$	$O(n \lg n)$	$O(n)$	Да	—	Сортировка объектов равной длины, имеющих «разряды». обычно это строки или целые числа. Алгоритм состоит в том, чтобы отсортировать объекты по разрядам, начиная от младших к старшим.
Сортировка подсчетом (Counting Sort)	$O(n)$	$O(n + k)$	$O(k)$	$O(k)$	Да	$O(n + k)$	Сортировка целых чисел, входящих в какой-то небольшой диапазон. Создаем массив длины диапазона $k$, каждый элемент которого будет показывать, сколько исходных элементов равны данному. Бежим по массиву и считаем количество вхождений каждого числа.
Сортировка Хэна (Han’s Sort)	$O(n \log \log n)$	$O(n \log \log n)$	$O(n \log \log n)$	$O(n)$	Да	$O(n \log \log n)$	Очень сложная сортировка, основанная на принадлежности ключей к целым числам. Использует экспоненциальное поисковое дерево Андерсона.
Многопоточная сортировка слиянием (Multithreaded merge sort)	$O(\frac>\log \frac>)$	$O(\frac>\log \frac>)$	$O(\frac>\log \frac>)$	$O(n)$	Да	$O(n \log n)$	Отличается от сортировки слиянием только тем, что при рекурсивном вызове будет создавать новый поток.
PSRS-сортировка (PSRS-sorting)	$O(\frac>\log \frac>)$	$O(\frac>\log \frac>)$	$O(\frac>\log \frac>)$	$O(N_^2)$	Нет	$O(n \log n)$	Разделим массив на $N_$ подмассива и запустим в каждой быструю сортировку. После этого объединим все эти подмассивы.

См. также

• Поисковые структуры данных
• Приоритетные очереди
• Поиск подстроки в строке

Источники информации

• Википедия — Алгоритмы сортировки
• Wikipedia —Sorting algorithm
• Хабрахабр — Бенчмарк алгоритмов сортировки
• Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 3-е изд. — М.: «Вильямс», 2013. — с. 174. — ISBN 978-5-8459-1794-2

• Дискретная математика и алгоритмы
• Сортировки
• Квадратичные сортировки
• Сортировки на сравнениях
• Многопоточные сортировки
• Другие сортировки

Какую временную сложность имеет алгоритм сортировки слиянием

Цель данной работы:

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

2. Краткие сведения из теории

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

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

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

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

2.2. Методы сортировки

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

В этой работе рассмотрим алгоритмы внутренней сортировки массивов элементов, так как они более важны большинству программистов в повседневной практике.

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

2.2.1. О сложности алгоритмов

При рассмотрении методов будем оперировать понятиями временной T и пространственной O теоретической сложности (в дальнейшем будем опускать слово «теоретическая») алгоритма, поэтому вкратце упомянем, что это такое.

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

Например, если число тактов (действий), необходимое для работы метода, выражается как 11*n 2 +19*n*log(n)+3*n+4, где n-размерность задачи, то мы имеем дело с алгоритмом со сложностью T(n 2 ). Фактически, мы из всех слагаемых оставляем только слагаемое, вносящее наибольший вклад при больших n (в этом случае остальными слагаемыми можно пренебречь) и игнорируем коэффициент перед ним.

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

Временная (пространственная) сложность не позволяет определить время (необходимый объем дополнительной памяти) работы алгоритма, но она позволяет оценить динамику роста времени (объема дополнительной памяти), необходимого для работы метода, при увеличении размерности задачи. Например, для алгоритма с временной сложностью T(n 2 ) при достаточно больших n можно утверждать, что при увеличении размера задачи (при сортировке — размера массива) в 3 раза время работы алгоритма увеличится в 3 2 =9 раз.

Если операция выполняется за фиксированное число шагов, не зависящее от размера задачи, то принято писать T(1).

Надо помнить, что перед одночленом, отражающим сложность, стоит некоторый коэффициент C. Поэтому алгоритмы с одинаковой сложностью могут сильно отличаться временем исполнения.

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

• максимальную сложность , или сложность наиболее неблагоприятного случая, когда метод работает дольше всего;
• среднюю сложность — сложность метода в среднем;
• минимальную сложность — сложность в наиболее благоприятном случае, когда метод справляется быстрее всего.

Алгоритмы, рассматриваемые здесь, имеют временные сложности T(n 2 ), T(n*log(n)), T(n). Минимальная сложность всякого алгоритма сортировки не может быть меньше T(n). Максимальная сложность метода, оперирующего сравнениями, не может быть меньше T(n*log(n)). Доказательство последнего факта можно найти в многочисленной серьезной теоретической литературе, посвященной проблемам сортировки. Однако есть методы, которые не сравнивают элементы между собой. Мы рассмотрим один из них — сортировку распределением.

Для дальнейшего изложения нам понадобится следующее тождество:

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

1. Сложность T(log(n)).

Из всех рассматриваемых здесь сложностей эта самая малая. Действительно, при достаточно большом n: log(n)

Эта сложность получается, если на каждом шаге метода выполняется некоторое постоянное число действий C и задача размерности n сводится к аналогичной задаче размерностью n/m, где m – целая положительная константа:

(При доказательстве этой и нижеследующих формул сложности используется метод математической индукции)

Тогда , что и требовалось доказать.

Примеры методов с такой сложностью вы можете найти в лабораторных работах по темам «Методы поиска», «Управление сбалансированными деревьями», «Управление b-деревьями».

Такая сложность получается в обычных итерационных процессах, когда на каждом шаге метода задача размерности n сводится к задаче размерности n-1, и при этом на каждом шаге выполняется некоторое постоянное число действий C, не зависящее от n:

1. F (1)=С*(n-1)=0;
2. Пусть F (n-1)=C*(n-2)

Тогда F (n)=C+ F (n-1)=C+C*(n-2)=C*(1+n-2)=C*(n-1), что и требовалось доказать.

Примером такой сложности может служит любой цикл, в котором число итераций прямо зависит от n. В этой работе такие методы можно найти при рассмотрении лабораторной работы по теме «Методы поиска». Также некоторые методы сортировки в лучшем случае (если массив уже отсортирован) выполняют порядка n действий, а сортировка распределением всегда требует порядка n действий.

1. Сложность T(n*log(n)).

Эта сложность получается, если на каждом шаге метода выполняется некоторое количество действий C*n, то есть зависящее от размера задачи прямопропорционально, и задача размерности n сводится к задаче размерностью n/m, где m – целая положительная константа:

Примеры алгоритмов с такой сложностью можно найти в лабораторной работе, посвященной сортировкам.

1. Сложность T(n 2 ).

Такая сложность получается, когда мы имеем два вложенных цикла, число итераций которых зависит от n прямопропорционально. Или другими словами, на каждом шаге метода задача размерности n сводится к задаче размерности n-1, и при этом выполняется некоторое количество действий C*n, то есть зависящее от n прямо пропорционально:

, что и требовалось доказать.

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

При рассмотрении алгоритмов сортировки прежде всего нас будет интересовать максимальная и средняя сложности метода, так как именно они, как правило, важны на практике. Максимальная сложность показывает поведение алгоритма в худшем случае, а средняя сложность – наиболее вероятное поведение при увеличении размера сортируемого массива. Сводные данные о сложности рассматриваемых методов можно найти в приложении 2 в конце работы.

Начнем разбор алгоритмов.

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

for i := 1 to N do begin B[k+1] := A[i]; end;

Слева от B[k+1] должны стоять элементы большие или равные B[k+1]. Значит число k складывается из количества элементов меньших A[i] и, возможно, некоторого числа элементов, равных A[i]. Условимся, что из равных мы будем учитывать только те элементы, которые в исходном массиве стоят левее A[i]. Теперь вычисление k можно записать следующим образом:

k := 0; for j := 1 to N do if (A[i]>A[j])or((A[i]=A[j])and(i>j)) then Inc(k);

Легко видеть, что этот алгоритм всегда имеет сложности T(n 2 ) (два вложенных цикла, зависящих от n линейно) и O(n) (результирующий массив).

В этой сортировке массив делится на 2 части: отсортированную и неотсортированную. На каждом шаге берется очередной элемент из неотсортированной части и «включается» в отсортированную часть массива.

Пусть отсортировано начало массива A[1], A[2], . A[i-1], а остаток массива A[i], . A[n] содержит неотсортированную часть. На очередном шаге будем включать элемент A[i] в отсортированную часть, ставя его на соответствующее место. При этом придется сдвинуть часть элементов, больших A[i], (если таковые есть) на одну позицию правее, чтобы освободить место для элемента A[i]. Но при сдвиге будет потеряно само значение A[i], поскольку в эту позицию запишется первый (самый правый — с самым большим индексом) сдвигаемый элемент. Поэтому прежде чем производить сдвиг элементов необходимо сохранить значение A[i] в промежуточной переменной.

Так как массив из одного элемента можно считать отсортированным, начнем с i=2.

Программа будет выглядеть так:

for i := 2 to n do begin Tmp := A[i]; j := i-1; while (A[j]>Tmp)and(j>1) do begin A[j+1] := A[j]; Dec(j) end; A[j+1] := Tmp; end;

Этот алгоритм также имеет максимальную и среднюю сложности T(n 2 ), но в случае исходно отсортированного массива внутренний цикл не будет выполняться ни разу, поэтому метод имеет T min (n). Можно заметить, что метод использует любой частичный порядок, и чем в большей степени массив исходно упорядочен, тем быстрее он закончит работу. В отличие от предыдущего метода, этот не требует дополнительной памяти.

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

Вместо включения A[i] в подмассив предшествующих ему элементов, его включают в подсписок, содержащий элементы A[i-h], A[i-2h], A[i-3h] и так далее, где h — положительная константа. Таким образом формируется массив, в котором «h- серии» элементов, отстоящих друг от друга на h, сортируются отдельно.

Конечно, этого недостаточно: процесс возобновляется с новым значением h, меньшим предыдущего. И так до тех пор, пока не будет достигнуто значение h=1.

В настоящее время неизвестна последовательность h i , h i-1 , h i-2 , . h 1 , оптимальность которой доказана. Для достаточно больших массивов рекомендуемой считается такая последовательность, что h i+1 =3h i +1, а h 1 =1. Начинается процесс с h m-2 , где m — наименьшее целое такое, что h m і n. Другими словами h m-2 первый такой член последовательности, что h m-2 і [n/9].

Теперь запишем алгоритм:

Step := 1; while Step < N div 9 do Step := Step*3 + 1; Repeat for k := 1 to Step do begin i := Step + k; while i = 1) and (A^[j]>x) do begin A^[j + Step] := A^[j]; Dec(j); end; A^[j + Step] := x; Inc(i, Step); end; end; Step := Step div 3; until Step=0;

Как показывают теоретические выкладки, которые мы приводить не будем, сортировке методом Шелла требуется в среднем 1,66n 1,25 перемещений.

В этих методах массив также делится на уже отсортированную часть A[i+1], A[i+1], . A[n] и еще не отсортированную A[1], A[2], . A[i]. Но здесь из неотсортированной части на каждом шаге мы извлекаем максимальный элемент. Этот элемент будет минимальным элементом отсортированной части, так как все большие его элементы мы извлечем на предыдущих шагах, поэтому ставим извлеченный элемент в начало отсортированной части.

При простом извлечении мы будем искать максимальный элемент неотсортированной части, просматривая ее заново на каждом шаге. Найдя положение максимального элемента поменяем его с A[i] местами.

for i := N downto 2 do begin MaxIndex := 1; for j := 2 to i do if A[j]>A[MaxIndex] then MaxIndex := j; Tmp := A[i]; A[i] := A[MaxIndex]; A[MaxIndex] := Tmp; end;

Простое извлечение во всех случаях имеет временную сложность T(n 2 ) (два вложенных цикла, зависящих от n линейно).

Древесная сортировка избегает необходимости каждый раз находить максимальный элемент. При следовании этому методу постоянно поддерживается такой порядок, при котором максимальный элемент всегда будет оказываться в A[1]. Сортировка называется древесной, потому что в этом методе используется структура данных, называемая двоичным деревом .

Двоичное дерево имеет элемент, называемый корнем . Корень, как и любой другой элемент дерева (называемый вершиной ), может иметь до двух элементов-сыновей. Все элементы, кроме корневого имеют элемент-родитель.

Условимся нумеровать вершины числами 1, 2, . сыновьями вершины с номером k будут вершины с номерами 2*k и 2*k+1, — как это сделано на рисунке. Как можно заметить, двоичное разложение номера вершины указывает путь к этой вершине от корня (0 — к левому сыну, 1 — к правому сыну). Например, 9 10 =1001 2 . Первую 1 двоичного разложения пропускаем (в начале всегда стоит 1). Затем идет 0, то есть от корня переходим к левому сыну (вершина номер 2 10 =10 2 ), потом снова 0 — переходим к левому сыну (вершина номер 4 10 =100 2 ), последней следует цифра 1 — переходим к правому сыну и как раз попадаем в вершину номер 9 10 =1001 2 . Значит номер элемента однозначно определяет его положение в дереве.

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

Пусть A[1]..A[n] — массив, подлежащий сортировке. Вершинами дерева будут числа от 1 до n; о числе A[i] мы будем говорить как о числе, стоящем в вершине i. В процессе сортировки количество вершин дерева будет сокращаться. Число вершин текущего дерева будем хранить в переменной k. Таким образом, в процессе работы алгоритма массив A[1]..A[n] делится на две части: в A[1]..A[k] хранятся числа на дереве, а в A[k+1] .. A[n] хранится уже отсортированная в порядке возрастания часть массива — элементы, уже занявшие свое законное место.

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

Договоримся о терминологии. Вершинами дерева считаются числа от 1 до текущего значения переменной k. У каждой вершины s могут быть сыновья 2*s и 2*s+1. Если оба этих числа больше k, то сыновей нет; такая вершина называется листом . Если 2*s=k, то вершина s имеет ровно одного сына (2*s).

Для каждого s из 1..k рассмотрим «поддерево» с корнем в s: оно содержит вершину s и всех ее потомков (сыновей, сыновей сыновей и т.д. — до тех пор, пока мы не выйдем из отрезка 1..k).

Вершину s будем называть регулярной , если стоящее в ней число — максимальный элемент s-поддерева; s-поддерево назовем регулярным , если все его вершины регулярны. (В частности, любой лист образует регулярное одноэлементное поддерево.)

Схема алгоритма такова:

k:= n . Сделать 1-поддерево регулярным; while k<>1 do begin . обменять местами A[1] и A[k]; k := k - 1; . восстановить регулярность 1-поддерева всюду end;

В качестве вспомогательной процедуры нам понадобится процедура восстановления регулярности s-поддерева в корне. Вот она:

 t := s; while ((2*t+1<=k) and (A[2*t+1]>A[t])) or ((2*t<=k) and (A[2*t]>A[t])) do begin if (2*t+1<=k) and (A[2*t+1]>=A[2*t]) then begin . обменять A[t] и A[2*t+1]; t := 2*t + 1; end else begin . обменять A[t] и A[2*t]; t := 2*t; end; end;

Чтобы убедиться в правильности этой процедуры, посмотрим на нее повнимательнее. Пусть в s-поддереве все вершины, кроме разве что вершины t, регулярны. Рассмотрим сыновей вершины t. Они регулярны, и потому содержат наибольшие числа в своих поддеревьях. Таким образом, на роль наибольшего числа в t-поддереве могут претендовать число в самой вершине t и числа, содержащиеся в ее сыновьях. (В первом случае вершина t регулярна, и все в порядке.) В этих терминах цикл можно записать так:

while наибольшее число не в t, а в одном из сыновей do begin if оно в правом сыне then begin . поменять t с ее правым сыном; t:= правый сын end else begin . поменять t с ее левым сыном; t:= левый сын end end

После обмена вершина t становится регулярной (в нее попадает максимальное число t-поддерева). Не принявший участия в обмене сын остается регулярным, а принявший участие может и не быть регулярным. В остальных вершинах s-поддерева не изменились ни числа, ни поддеревья их потомков (разве что два элемента поддерева переставились), так что регулярность не нарушилась.

Эта же процедура может использоваться для того, чтобы сделать 1-поддерево регулярным на начальной стадии сортировки:

k := n; u := n; u регулярны > while u<>0 do begin . восстановить регулярность u-поддерева в корне; u:=u-1; end;

Теперь запишем процедуру сортировки на паскале:

procedure Sort; Var u, k: Integer; procedure Exchange(i, j: Integer); Var Tmp: Integer; begin Tmp := x[i]; A[i] := A[j]; A[j] := Tmp; end; procedure Restore(s: Integer); Var t: Integer; begin t:=s; while ((2*t+1<=k) and (A[2*t+1]>A[t])) or ((2*t<=k) and (A[2*t]>A[t])) do begin if (2*t+1<=k) and (A[2*t+1]>=A[2*t]) then begin Exchange(t, 2*t+1); t := 2*t+1; end else begin Exchange(t, 2*t); t := 2*t; end; end; end; begin k:=n; u:=n; while u<>0 do begin Restore(u); Dec(u); end; while k<>1 do begin Exchange(1, k); Dec(k); Restore(1); end; end;

Преимущество этого метода перед другими в том, что он, имея T max (n*log(n)) (внутри внешнего цикла зависящего от n линейно вызывается процедура Restore, требующая порядка log(n) действий), при сортировке не требует дополнительной памяти порядка n.

Как следует из названия метода он сортирует массив путем последовательных обменов пар элементов местами.

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

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

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

for i := N-1 downto 1 do begin Flag := false; for j := 1 to i do if a[j]>a[j+1] then begin Tmp := A[j]; A[j] := A[j+1]; A[j+1] := Tmp; Flag := true; end; if not Flag then Break; end;

Этот алгоритм имеет среднюю и максимальную временные сложности T(n 2 ) (два вложенных цикла, зависящих от n линейно) и не требует дополнительной памяти за исключением памяти для фиксированного числа переменных (i, j, Tmp, Flag). Введение переменной Flag и прерывание работы в случае отсортированного массива позволяет свести минимальную временную сложность к T(n).

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

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

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

Запишем то, что мы сейчас сформулировали:

procedure Sort; procedure QuickSort(a, b: Longint); Var x: Longint; begin x := элемент_выбранный_средним; . деление на три части: 1) A[a]..A[i]; 2) A[i+1]..A[j-1]; 3) A[j]..A[b] if i>a then QuickSort(a, i); if b>j then QuickSort(j, b); end; begin Sort(1, N); end;

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

i := A[l]; y := A[(l+r)div 2]; j := A[r]; if i=j then x := (l+r)div 2 else if i>=j then x := r else x := l;

Теперь нам надо разделить массив относительно элемента A[x] так, чтобы сначала следовали элементы, меньшие A[x], затем сам элемент A[x], а потом уже элементы, большие или равные A[x]. Для этого мы, двигаясь слева найдем первый элемент A[i], больший A[x], и, двигаясь справа, — первый элемент A[j], меньший A[x]. Если i окажется меньше j, то это значит, что массив еще не поделен на три искомых части, в таком случае обменяем местами элементы A[i] и A[j], а затем продолжим поиск слева от A[i] и справа от A[j].

i := l; j := r; x := A[x]; repeat while A[i] < x do Inc(I); while x < A[j] do Dec(j); if i j;

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

Теперь осталось только собрать вместе части программы:

procedure Sort; procedure QuickSort(a, b: Longint); Var x: Longint; begin i := A[l]; y := A[(l+r)div 2]; j := A[r]; if i=j then x := (l+r)div 2 else if i>=j then x := r else x := l; i := l; j := r; x := A[x]; repeat while A[i] < x do Inc(i); while x < A[j] do Dec(j); if i j; if l-j
В худшем случае этот алгоритм дает временную сложность T max (N 2 ) (для случая, когда все выборки «среднего» элемента оказались неудачны), но как показывают теоретические исследования вероятность такого случая очень мала. В среднем же и в лучшем случае получим T(N*log(N)).
Этот метод сортирует массив последовательным слиянием пар уже отсортированных подмассивов, поэтому его и назвали сортировкой слиянием.
Пусть k - положительное целое число. Разобьем массив A[1]..A[n] на отрезки длины k. (Первый - A[1]..A[k], затем A[k+1]..A[2k] и т.д.) Последний отрезок будет неполным, если n не делится нацело на k. Назовем массив k-упорядоченным, если каждый из этих отрезков длины k упорядочен.
Ясно, что любой массив 1-упорядочен, так как его подмассивы длиной 1 можно считать упорядоченными. Если массив k-упорядочен и n
Теперь запишем общую схему алгоритма:
k:=1; while k < n do begin . преобразовать k-упорядоченный массив в 2k-упорядоченный; k := 2 * k; end;
Рассмотрим процедуру преобразования k-упорядоченного массива в 2k-упорядоченный. Сгруппируем все подмассивы длины k в пары подмассивов. Теперь пару упорядоченных подмассивов сольем в один упорядоченный подмассив. Проделав это со всеми парами, мы получим 2k-упорядоченный массив:
t:=0; while t + k < n do begin p := t; q := t+k; . r := min(t+2*k, n); . сливаем два подмассива A[p..q-1] и A[q..r] t := r; end;
Слияние требует вспомогательного массива для записи результатов слияния - обозначим его B. Через p0 и q0 обозначим номера последних элементов участков, подвергшихся слиянию, s0 - последний записанный в массив B элемент. На каждом шаге слияния производится одно из двух действий:
Inc(p0); Inc(s0);
B[s0+1]:=A[q0+1]; Inc(q0); Inc(s0);
Первое действие (взятие элемента из первого отрезка) может производиться при двух условиях:
(1) первый отрезок не кончился (p0 < q);
(2) второй отрезок кончился (q0 = r) или не кончился, но элемент в нем не меньше [(q0 < r) и (A[p0+1] 


Аналогично для второго действия. Итак, получаем
p0 := p; q0 := q; s0 := p; while (p0<>q)or(q0<>r) do begin if (p0
(Если оба отрезка не кончены и первые невыбранные элементы в них равны, то допустимы оба действия; в программе выбрано первое.)
Осталось собрать программу в одно целое:
k := 1; while k < N do begin t := 0; while t+k < N do begin p := t; q := t+k; if t+2*k>N then r := N else r := t+2*k; p0 := p; q0 := q; s0 := p; while (p0<>q) or (q0<>r) do begin if (p0
Сразу же бросается в глаза недостаток метода – он требует дополнительную память размером порядка N (для хранения вспомогательного массива). Но как и для древесной сортировки, его временная сложность всегда пропорциональна N*log(N) (так как преобразование k-упорядоченного массива в 2k-упорядоченный требует порядка N действий и внешний цикл по k совершает порядка log(N) итераций).
Сортировка распределением интересна тем, что она сортирует массив, не сравнивая элементы друг с другом.
Рассмотрим сначала вырожденный случай сортировки распределением, а затем более общий.
Пусть каждый элемент массива может принимать M (например, от 1 до M) фиксированных значений. Заведем массив Amount, первоначально обнулив его. Затем для каждого i подсчитаем количество элементов массива A, равных i, и занесем это число в Amount[i]:
for i := 0 to M do Amount[i] := 0; for i := 1 to N do Inc(Amount[A[i]]);
Теперь в первые Amount[1] элементов массива A запишем 1, в следующие Amount[2] элементов массива A запишем 2 и т.д. до тех пор, пока не дойдем до конца массива A (заметим, что в то же время мы окажемся в конце массива Amount):
p := 1; for i := 0 to M do for j := 1 to Amount[i] do begin A[p] := i; Inc(p); end;
Несмотря на то, что здесь два внешних цикла на этом участке алгоритма выполняется порядка N действий. Это следует из того, что . Поэтому временную сложность метода можно оценить как T(M+N) (M появляется в сумме, так как изначально надо обнулить массив Amount, а это требует M действий). Пространственная сложность в этом случае равна O(M), поскольку требуется дополнительная память размером порядка M.
Недостатком этого метода является то, что требуется дополнительная память размером порядка M, а это может оказаться недопустимым из-за большого значения M. Но, если M>>N, то есть способ уменьшить объем требуемой дополнительной памяти, который мы сейчас и рассмотрим.
Пусть мы можем завести дополнительную память размером M+N, а элементы массива могут принимать значения от 0 до S, причем S>>M.
Каждый элемент этого массива можно представить в M-ичной системе счисления и разбить на K цифр этой системы счисления.
Заведем M списков общей суммарной длиной порядка N (это можно сделать, ограничившись дополнительной памятью O(M+N)).
Наш алгоритм можно представить следующим образом:
for i := K downto 1 do begin for j := 1 to N do begin L:=; . занести A[j] в L-ный список; end; . очистить массив A for j := 1 to M do . дописать элементы j-ого списка в массив A end;
Итак, как видно из приведенной выше программы, на каждом шаге метода производится сортировка элементов массива по значению i-ого разряда. При этом производится промежуточное распределение элементов массива по спискам в зависимости от значения соответствующего разряда этих элементов. Во время распределения очень важно сохранить при записи в списки порядок следования элементов, чтобы не нарушить порядок, достигнутый на предыдущих шагах.
Индукцией по i легко доказать, что после i шагов любые два числа, отличающиеся только в i последних разрядах, идут в правильном порядке.
Достигнув i=1, мы получим полностью отсортированный массив.
Как нетрудно заметить, если положить S=M, то отпадает необходимость заводить списки и производить запись в них: в j–ый список будут попадать только числа, равные j. В этом случае достаточно хранить лишь размеры списков, то есть подсчитать количество элементов, равных j, для всех j от 1 до S. А потом просто заново заполнить массив A в соответствии с этими количествами. Что мы и делали в случае вырожденной сортировки.
Интересно, что временная сложность этого метода T(K*N), а если учесть, что K фактически является константой, то мы получаем гарантированную (минимальную, среднюю и максимальную) линейную сложность. Но недостатком этого метода является необходимость выделять дополнительную память размером порядка M+N. Если бы не это ограничение, можно было бы считать этот метод самым эффективным при больших значениях N.
2.3. Сравнительный анализ
Для проведения экспериментального сравнительного анализа различных методов сортировки была разработана программа, которая в автоматическом режиме подсчитывала время, требуемое для каждого метода сортировки. Для чистоты эксперимента сортировка всеми методами проводилась на одинаковых наборах входных данных, затем формировался новый набор данных, и они опять подвергались сортировке различными методами. Таким образом было выполнено 60 циклов сортировки, подсчитано среднее время, которое потребовалось каждому методу, чтобы отсортировать входной массив. Для более полного анализа методов в каждом цикле сортировки сортировка проводилась для размерностей 500, 1000, 3000, 5000, 8000, 10000, 30000, 60000. Это дало возможность проследить динамику роста требуемого для сортировки времени. Также проверялось, как ведут себя методы на различных входных данных: упорядоченных в прямом порядке, упорядоченных в обратном порядке и случайных.
Ниже приведены таблицы, которые выдала составленная программа.
а) Для массива, заполненного случайными элементами:


Похожие публикации:

Dbus что это
Как перенести загрузчик с одного диска на другой
Как сделать аутентификацию на сайте
Как убрать закругленные углы в css