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

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

Алгоритм:
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)

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

Алгоритм сортировки, который сортирует неупорядоченную «стопку блинов». В этом алгоритме выполняется операция переворачивания участка стека.

Алгоритм:
Шаг 1. Найдите самый большой блин.
Шаг 2. Переверните стопку, чтобы переместить самый большой «блин» на вершину стека.
Шаг 3. Повторите шаги 2 и 3, но теперь учитывая оставшуюся неотсортированную часть стопки.

Продолжайте пока вся стопка не будет отсортирована: «самый большой блин окажется внизу, а самый маленький — наверху».

Сложность алгоритма:
Лучший случай: O(n) — если массив уже отсортирован, алгоритм может завершиться быстрее, так как будет выполнять меньше переворотов.
Средний случай: O(n²) — алгоритм требует порядка n итераций для нахождения максимального элемента в неотсортированной части массива, и для каждой итерации может потребоваться до n переворотов.
Худший случай: O(n²) — когда элементы находятся в обратном порядке, алгоритму потребуется максимальное количество переворотов для сортировки.

Шейкерная сортировка

Простой алгоритм сортировки, являющийся разновидностью алгоритма пузырьковой сортировки.

Алгоритм:
1. Проход вправо:
- Сравниваем соседние элементы с крайнего левого элемента.
- Если текущий элемент больше следующего элемента, меняем их местами.
- Продолжайте этот процесс, перемещаясь слева направо, пока не дойдете до конца списка. После этого прохода самый большой элемент «всплывает» в конец списка.

2. Проход влево:
- Теперь выполните проход справа налево, сравнивая и меняя местами соседние элементы.
- Если текущий элемент меньше предыдущего, поменяйте их местами.
- Продолжайте этот процесс, перемещаясь справа налево, но остановитесь перед последним отсортированным элементом. После этого прохода наименьший элемент «всплывает» в начало списка.

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

Gnome Sort

Простой алгоритм сортировки. Он называется «Сортировка гномов», потому что напоминает садового гнома, сортирующего ряд цветочных горшков :)

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

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

Odd-Even Sort

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

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

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

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

Сортировка расчёской

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

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

Сложность: O(n*log(n))

Голубиная сортировка

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

Работа алгоритма:
Шаг 1: Найдите минимальное (min) и максимальное (max) значения в массиве. Также найдите range как «max-мin+1».
Шаг 2: Создайте массив изначально пустых «ячеек» того же размера, что и диапазон.
Шаг 3: Посетите каждый элемент массива, а затем поместите каждый элемент в свою ячейку. Элемент arr[i] помещается в ячейку с индексом arr[i] – min.
Шаг 4: Запустите цикл по всему массиву ячеек по порядку и поместите элементы из непустых ячеек обратно в исходный массив.

Сложность: O(n+range)

Циклическая сортировка

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

Алгоритм:
Шаг 1: Инициализируйте переменную pos значением 0.
Шаг 2: Для каждого элемента массива сравните его со всеми остальными элементами справа от него. Если есть какие-либо элементы, которые меньше текущего элемента, увеличьте pos.
Шаг 3: Если pos по-прежнему равен 0 после сравнения первого элемента со всеми остальными элементами, перейдите к следующему элементу и повторите шаг 2.
Шаг 4: Как только будет найден меньший элемент, замените текущий элемент первым элементом в его цикле. Затем цикл продолжается до тех пор, пока текущий элемент не вернется в исходное положение.

Повторяйте шаги 3–5, пока не будут завершены все циклы. Теперь массив отсортирован.

Сложность: O(n^2)

Нитевидная сортировка

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

Алгоритм:
Пусть input[] — входной список, а output[] — выходной список.

Шаг 1: Создайте еще один пустой список sublist и переместите в него первый элемент input.
Шаг 2: Для каждого элемента x из input проверьте, превышает ли x последний добавленный элемент в список.
- Если да, удалите x из input и добавьте в конец sublist.
- Если нет, игнорируйте x (сохраните его в input)
Шаг 3: Объединить подсписок в outputp.

Повторите для оставшихся элементов в input и текущих элементов в output.

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

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

Алгоритм сортировки, названный в честь понятия «битонической последовательности».

Для эффективной работы алгоритма длина списка должна быть степенью 2.

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

Сложность: O(log^2n)

Stooge Sort

Простой алгоритм сортировки, который использует рекурсию для упорядочивания элементов в массиве. Он был разработан в 1970 году языком программирования Чарльзом Хоаром, но получил свое название благодаря трём бестолковым импровизаторам (stooges) в комедийном эпизоде.

Алгоритм:
Берём отрезок массива (вначале это весь массив) и сравниваем элементы на концах отрезка. Если слева больше чем справа, то, естественно, меняем местами.
Затем, если в отрезке не менее трёх элементов, то тогда:
1) вызываем Stooge sort для первых 2/3 отрезка;
2) вызываем Stooge sort для последних 2/3 отрезка;
3) снова вызываем Stooge sort для первых 2/3 отрезка.

Сложность: O(n^(log3/log1.5))

Бисерная сортировка

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

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

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

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

Список будет отсортирован в порядке возрастания.

Сложность: O(n^2)

Алгоритм линейного поиска

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

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

Иногда конец списка достигается без обнаружения целевого элемента, и в этом случае поиск не увенчается успехом, и для обозначения этого часто возвращается специальное значение (например, -1).

Сложность: O(n)

Бинарный поиск

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

Шаг 1: Установите два указателя: один в начале списка и один в конце списка.
Шаг 2: Вычислите среднее положение между левым и правым указателями и сравните элемент в средней позиции с целевым элементом.
- Если элемент в средней позиции соответствует целевому элементу, поиск успешен и возвращается позиция (индекс) целевого элемента.
- Если средний элемент больше целевого элемента, удалите правую половину пространства поиска, переместив правый указатель на одну позицию перед средним.
- Если средний элемент меньше целевого элемента, удалите левую половину пространства поиска, переместив левый указатель на одну позицию после середины.

Сложность: O(log n)

Ternary Search

Алгоритм поиска элемента в упорядоченном массиве.

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

Сложность: O(log3 N)

Jump Search

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

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

Сложность: O(sqrt(n))

Интерполяционный поиск

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

Алгоритм:
Шаг 1: В цикле вычислите значение «pos», используя формулу положения датчика.
Шаг 2: Если это совпадение, верните индекс элемента и выйдите.
Шаг 3: Если элемент меньше arr[pos], вычислите положение зонда левого подмассива. В противном случае вычислите то же самое в правом подмассиве.
Шаг 4: Повторяйте до тех пор, пока не будет найдено совпадение или пока подмассив не уменьшится до нуля.

Сложность: O(log(log(n)))

Exponential Search

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

Включает в себя два этапа:

Шаг 1: Найти диапазон, в котором присутствует элемент
Шаг 2: Выполните двоичный поиск в найденном выше диапазоне.

Сложность: O(log n)