Алгоритмы сортировки / Sort Algorithms

В информатике алгоритм сортировки называется - алгоритмом, который упорядочивает элементы в списке.

Сортировка пузырьком (Bubble Sort)

---

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

Временная сложность:		Пространственная сложность:
Лучшее:	$O(n$)	Всего:	$O(1)$
Среднее:	$O(n^2$)	Дополнительно:
Худшее:	$O(n^2$)

---

Шейкерная/коктейльная сортировка (Shaker/Cocktail Sort)

---

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

Временная сложность:		Пространственная сложность:
Лучшее:	$O(n$)	Всего:	$O(1)$
Среднее:	$O(n^2$)	Дополнительно:
Худшее:	$O(n^2$)

---

Сортировка вставками (Insertion Sort)

---

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

Временная сложность:		Пространственная сложность:
Лучшее:	$O(n$)	Всего:	$O(n)$
Среднее:	$O(n^2$)	Дополнительно:	$O(1)$
Худшее:	$O(n^2$)

---

Сортировка Шелла (Shell Sort)

---

Алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Идея метода Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга.

Временная сложность:		Пространственная сложность:
Лучшее:	$O(n$ $log$ $n$)	Всего:	$O(n)$
Среднее:	Зависит от выбранных шагов	Дополнительно:	$O(1)$
Худшее:	$O(n^2$)

---

Сортировка деревом (Tree Sort)

---

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

Временная сложность:		Пространственная сложность:
Лучшее:	$O(n$ $log$ $n$)	Всего:	$O(n)$
Среднее:	$O(n$ $log$ $n$)	Дополнительно:
Худшее:	$O(n^2$)

---

Пирамидальная сортировка (или сортировка кучей, Heap Sort)

---

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

Двоичная куча — это законченное двоичное дерево, в котором элементы хранятся в особом порядке: значение в родительском узле больше (или меньше) значений в его двух дочерних узлах. Первый вариант называется max-heap, а второй — min-heap. Куча может быть представлена двоичным деревом или массивом.

Временная сложность:		Пространственная сложность:
Лучшее:	$O(n$)	Всего:	$O(n)$
Среднее:	$O(n$ $log$ $n$)	Дополнительно:	$O(1)$
Худшее:	$O(n$ $log$ $n$)

---

Сортировка выбором (Select Sort)

---

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

Временная сложность:		Пространственная сложность:
Лучшее:	$O(n^2$)	Всего:	$O(1)$
Среднее:	$O(n^2$)	Дополнительно:
Худшее:	$O(n^2$)

---

Гномья сортировка (Gnome Sort)

---

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

Временная сложность:		Пространственная сложность:
Лучшее:	$O(n$)	Всего:	$O(1)$
Среднее:	$O(n^2$)	Дополнительно:
Худшее:	$O(n^2$)

---

Поразрядная сортировка (Radix Sort)

---

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

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

Так как выравнивать сравниваемые записи относительно друг друга можно в разную сторону, на практике существуют два варианта этой сортировки. Для чисел они называются в терминах значимости разрядов числа, и получается так: можно выровнять записи чисел в сторону менее значащих цифр (по правой стороне, в сторону единиц — LSD от англ. least significant digit) или более значащих цифр (по левой стороне, со стороны более значащих разрядов — MSD от most significant digit).

Временная сложность:		Пространственная сложность:
Лучшее:	$O(n$)	Всего:	$O(w + n$)
Среднее:	$O(n$ $log$ $n$)	Дополнительно:
Худшее:	$O(w * n$)

• Где $w$ — количество бит, требуемых для хранения каждого ключа.

---

Сортировка слиянием (Merge Sort)

---

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

Для решения задачи сортировки эти три этапа выглядят так:

.1. Сортируемый массив разбивается на две части примерно одинакового размера;
.2. Каждая из получившихся частей сортируется отдельно, например — тем же самым алгоритмом;
.3. Два упорядоченных массива половинного размера соединяются в один.

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

3.1. Соединение двух упорядоченных массивов в один. Основную идею слияния двух отсортированных массивов можно объяснить на следующем примере. Пусть мы имеем два уже отсортированных по возрастанию подмассива. Тогда:

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

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

Временная сложность:		Пространственная сложность:
Лучшее:	$O(n$ $log$ $n$)	Для списка:	$O(1$)
Среднее:	$O(n$ $log$ $n$)	Для массива:	$O(n$)
Худшее:	$O(n$ $log$ $n$)

---

Быстрая сортировка (Quick Sort)

---

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

Общая идея алгоритма состоит в следующем:

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

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

Временная сложность:		Пространственная сложность:
Лучшее:	$O(n$ $log$ $n$)	Всего:	$O(n$)
Среднее:	$O(n$ $log$ $n$)	Дополнительно:	$O$($log$ $n$)
Худшее:	$O(n^2$)

• При разделении на 3 части лучшее время: $O(n)$

---

Сложность алгоритмов / Algorithm complexity

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

Пространственную сложность оценивают по объему памяти, необходимый программе для её выполнения.

Подробнее о сложности алгоритов

---

$O(1)$ — константная сложность

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

$O(n)$ — линейная сложность

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

$O(log$ $n)$ — логарифмическая сложность

Простейший пример — бинарный поиск. Если массив отсортирован, мы можем проверить, есть ли в н ем какое-то конкретное значение, методом деления пополам. Проверим средний элемент, если он больше искомого, то отбросим вторую половину массива — там его точно нет. Если же меньше, то наоборот — отбросим начальную половину. И так будем продолжать делить пополам, в итоге проверим $log$ $n$ элементов.

$O(n^2)$ — квадратичная сложность

Такую сложность имеет, например, алгоритм сортировки вставками. В канонической реализации он представляет из себя два вложенных цикла: один, чтобы проходить по всему массиву, а второй, чтобы находить место очередному элементу в уже отсортированной части. Таким образом, количество операций будет зависеть от размера массива как $n * n$, т. е. $n^2$.

---