Коллекция алгоритмов

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

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

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

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

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

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

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

Сортировка слияниями. Пусть есть два небольших массива. Если их слить в один и на каждом шаге слияния для переброски в новый массив, выбирать наименьший элемент из двух массивов, то массив-результат окажется полностью упорядоченным. Отсюда идея. Разобъем исходный массив на много маленьких. Маленькие объеденим по два и каждую пару сольем в больший массив. Затем объединим по два множество полученных массивов и сольем их и так до тех пор пока не останется один большой и естественно полностью упорядоченный массив.

Сортировка подсчетом. Идея алгоритма заключается в простом подсчете количества вхождений каждого числа в массив. Это делается так: выполним один проход массива и для каждого числа из отрезка [0, max] подсчитаем сколько раз оно встретится. Вычисленные количества сохраним в специальном массиве счетчиков. Затем запишем в массив - результат (а это может быть и исходный массив) каждое число столько раз, чему равно значение соответствующего ему счетчика, то есть, сколько раз оно встретилось. К сожалению алгоритм может работать только с очень специальным массивом, состоящим из целых чисел полностью заполняющих отрезок [0, max]

Алгоритмы на графах

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

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

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

Алгоритм Краскала. Алгоритм поиска минимального остовного дерева имеющего своим корнем одну из вершин графа. Краскал предлагает делать это достраивая уже имеющееся дерево, добавляя в него на каждом шаге новое ребро.

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

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

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

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

Вычислительные алгоритмы

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

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

Перевод дробной части десятичного числа в двоичное представление. Обычно говоря о переводе числа из одной системы счисления в другую, имеют ввиду целые числа, но не менее важно понимать, что делать с дробной частью. Её перевод существенно отличается по арифметике алгоритма.

Алгоритмы шифрования

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