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

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

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

Sentinel Linear Search

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

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

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

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

Поиск в глубину

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

Алгоритм:

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

Поиск в ширину

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

Алгоритм:

Шаг 1: Выберите начальную вершину (или узел), чтобы начать обход.
Шаг 2: Посетите выбранную вершину и отметьте ее как посещенную (чтобы она не посещалась повторно).
Шаг 3: Исследуйте всех непосещенных соседей текущей вершины на текущем уровне.
Шаг 4: Используйте очередь для управления обходом. Поставьте в очередь непосещенных соседей.
Шаг 5: Исключить из очереди следующую вершину, чтобы она стала новой текущей вершиной.
Шаг 6: Продолжайте процесс посещения, исследования и постановки в очередь, пока не будут посещены все вершины.

Алгоритм Дейкстры

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

Ключевые идеи:
- Кратчайший путь из одного источника.
Алгоритм Дейкстры фокусируется на поиске кратчайшего пути от одной исходной вершины ко всем остальным вершинам графа.

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

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

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