.

Сортировка пузырьком

Это один из простейших алгоритмов сортировки. Он не самый эффективный, но является фундаментальным шагом для погружения в мир алгоритмов.

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

Ключевые моменты:
- Пузырьковая сортировка проста для понимания, но неэффективна для больших списков.
- Его временная сложность в наихудшем случае равна O(n^2), что делает его менее практичным для реальных сценариев.
- Это хорошая отправная точка для понимания концепции сравнения и замены элементов для сортировки.

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

Это простой и интуитивно понятный алгоритм сортировки.
Он неоднократно находит самый маленький (или самый большой) элемент из неотсортированной части массива и заменяет его первым неотсортированным элементом.

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

Сложность алгоритма:
В лучшем случаи: O(n^2)
В cреднем: O(n^2)
В худшем: O(n^2)

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

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

Алгоритм:
1. Начинаем с первого элемента, который считается отсортированным.
2. Перебираем неотсортированную часть массива, беря по одному элементу за раз и сравниваем его с элементами в отсортированной части массива.
3. Сдвигаем элементы в отсортированной части массива вправо, пока не найдем правильную позицию для текущего элемента.
4. Как только правильная позиция найдена, вставляем текущий элемент в отсортированную часть массива.
5. Продолжаем этот процесс, пока не будет отсортирован весь массив.

Сложность алгоритма:
В лучшем случаи: O(n)
В cреднем: O(n^2)
В худшем: O(n^2)

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

Это алгоритм сортировки по принципу «разделяй и властвуй», который эффективно сортирует элементы, разделяя входные данные на более мелкие подзадачи, сортируя их, а затем объединяя их вместе.

Алгоритм:
1. Рекурсивно разделите входной массив на две половины, пока каждый подмассив не будет содержать только один элемент.
2. Отсортируйте каждый из подмассивов индивидуально.
3. Объедините отсортированные подмассивы вместе, чтобы создать один полностью отсортированный массив. Это достигается путем сравнения элементов двух подмассивов и их объединения в порядке возрастания.
4. Объединенный результат представляет собой отсортированный массив.

Сложность алгоритма:
В лучшем случаи: O(n logn)
В cреднем: O(n logn)
В худшем: O(n logn)

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

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

Алгоритм:
1. Выбор «pivot» из входного массива. (Его выбор может существенно повлиять на производительность алгоритма. Это может быть: первый, последний или случайный элемент).
2. Разделение элементов массива так, чтобы все элементы меньше «pivot» находились перед ним, а все элементы выше «pivot» — после нее.
3. Рекурсивное примените алгоритма быстрой сортировки к подмассиву элементов, меньших опорного, и к подмассиву элементов, превышающих опорный.
4. Продолжайте этот процесс, пока весь массив не будет отсортирован.

Сложность алгоритма:
В лучшем случаи: O(n logn)
В cреднем: O(n logn)
В худшем: O(n^2)

HeapSort

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

Алгоритм:
1. Преобразование входного массива в максимальную кучу. Максимальная куча — это двоичное дерево, в котором родительский узел больше или равен дочерним узлам.
2. Начиная с конца кучи (последний элемент массива), поменяйте местами корневой элемент (максимальный элемент в куче) с последним элементом.
3. После каждой замены уменьшите размер кучи на единицу и убедитесь, что свойство max-heap сохраняется для остальных элементов.
4. Повторяйте этот процесс, пока весь массив не будет отсортирован.

Сложность алгоритма: O(n logn)

Сортировка подсчётом

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

Алгоритм:
1. Определение диапазона входных значений и создание вспомогательного массива размером, равным диапазону значений.
2. Подсчет частоты каждого отдельного элемента, сопоставляя его с индексами в массиве подсчета.
3. Создание выходного массива того же размера, что и входной массив.
4. Размещаем элементы в зависимости от вспомогательного массива в новый отсортированный массив.

Cложность: O(N + K), где N — количество элементов во входном массиве, а K — диапазон входных данных.

Поразрядная сортировка

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

Алгоритм:
1. Определить необходимое количество проходов (зависит от количества цифр или символов в максимальном элементе)
2. Создание 10 сегментов (0–9) для каждой позиции цифры (для чисел с основанием 10) или 26 сегментов (A–Z) для каждой позиции символа (для букв верхнего регистра).
3. Распределение элементов по сегментам, начиная с младшей значащей цифры.
4. Сортировка элементов в каждом сегменте, используя стабильный алгоритм сортировки
5. Формирование частично отсортированного массива.
6. Повторение процесса до тех пор пока не получится отсортированный массив.

Сложность:
В лучшем случаи: O(n)
В худшем: O(n*k)

Bucket sort

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

Бакет (bucket — ведро) — это сущность для организации хранения в хранилище.

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

Сложность алгоритма: O(n)

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

Это алгоритм сортировки, который является расширением алгоритма сортировки вставками. Сортировка Шелла сортирует элементы, удаленные друг от друга на расстояние D, а затем постепенно сокращает разрыв между ними.

Есть огромное количество методов выбора числа D:
1. Самый просто пример это D = n / 2, D2 = D/2 … Dn =1
2. Предложение Хиббарда: проверить на всем N ^i — 1<= N. 
3. Числа Седжвика и много много другого.

Основные шаги в сортировке:
1. Выбрать расстояние D
2. Сформировать подмассивы на основе данного массива и расстояния D.
3. Применяем сортировку вставками к каждому подмассиву
4. Собрать массив
Повторять эти шаги пока массив не будет отсортирован.

Сложность алгоритма:
В лучшем случаи: O(n)
В cреднем: O(n (logn)^2)
В худшем: O(n log^2n)

Tim Sort

Это высокоэффективный и стабильный алгоритм сортировки,, который сочетает в себе элементы сортировки слиянием и сортировки вставками.

Алгоритм:
1. Разделение входного массива на более мелкие сегменты, называемые «runs». Минимальный размер run (minrun) определяется на основе n, исходя из следующих принципов:
- Не должно быть слишком большим, тк в дальнейшем применена сортировка вставками
- Не должно быть слишком маленьким, так как чем меньше run, тем больше итераций слияния придётся выполнить.
- Оптимальная величина n/minrun - степень двойки
2. Сортировка runs с помощью сортировки вставками.
3. Объединение соседних runs с помощью сортировки слияния

Сложность алгоритма:
В лучшем случаи: O(n)
В cреднем: O(n logn)
В худшем: O(n logn)