Как и многое другое, алгоритмы бывают разных типов, каждый из которых так же важен, как и следующий в своей области применения.
Несмотря на то, что в этой статье я коснусь только одного типа алгоритмов, крайне важно знать ряд других существующих типов.
Ниже приведен неполный список некоторых категорий алгоритмов, многие из которых будут рассмотрены в следующих публикациях.
Типы алгоритмов
- Инкрементальные алгоритмы
- Простые рекурсивные алгоритмы
- Алгоритмы обратного отслеживания
- Рандомизированные алгоритмы
- Алгоритмы разделяй и властвуй
- Алгоритмы грубой силы
- Алгоритмы динамического программирования
- Жадные алгоритмы
Без лишних слов, давайте перейдем к описываемым алгоритмам.
Инкрементальные алгоритмы
Проще говоря, инкрементный алгоритм - это алгоритм, который находит последовательность решений, которые строятся постепенно и постоянно адаптируются к изменениям входных данных. Эти типы алгоритмов известны своей сверхъестественной способностью адаптироваться к изменениям входных данных без необходимости постоянных повторных вычислений.
Идеальный сценарий для использования дополнительных алгоритмов:
- Существует большой объем данных, например, большая база данных или значительно большой график.
- Данные, которые существуют с течением времени, подвержены ряду относительно небольших изменений.
- Данные должны обрабатываться полезным образом.
- Важно, чтобы данные обновлялись в реальном времени независимо от их объема.
Инкрементальные алгоритмы решают проблему необходимости пересчитывать набор данных после каждого небольшого изменения в наборе данных, независимо от того, сколько минут оно длится. Это выполняется путем обработки изменения и отправки его (только изменения) по сети. Сжатие видео основано на этом принципе.
Некоторые языки легко подходят для инкрементальных алгоритмов. Подходящим классом этих языков является тот, который поддерживает функциональное реактивное программирование.
Следует отметить, что не существует известного решения для дополнительных алгоритмов во всех областях. В пространственном измерении реляционная алгебра является относительно инкрементальной, тогда как функциональное реактивное программирование мало используется в этом измерении.
Примером алгоритма, использующего поэтапный подход к созданию решения проблемы, является сортировка вставкой.
Следует отметить, что не существует известного решения для дополнительных алгоритмов во всех областях.
Вставка сортировки
Алгоритм сортировки вставкой решает проблему сортировки. Проблема сортировки ставит вопрос о том, как отсортировать заданное множество N, состоящее из числовых данных x1, x2, x3,…, xi, в порядке, который явно определен.
Поэтому дано:
N = { x1, x2, x3, …, xi | x1, .., xi 𝜖 R }
Элементы указанного выше набора не расположены в конкретно определенном порядке. Сортировка вставкой решает эту проблему, работая с набором чисел N и генерируя перестановку этого набора в соответствии с правилом порядка.
Чтобы объяснить это дальше, давайте определим два критерия, которым необходимо следовать:
- Операция сортировки вставкой сортировки представлена функцией 𝑓 (𝓝)
- Наша операция сортировки строго генерирует перестановку множества 𝓝, в которой все последовательные элементы расположены в порядке возрастания.
Следуя двум критериям, приведенным выше, мы можем определить нашу процедуру сортировки вставками следующим образом:
𝑓 (𝓝) = {n1, n2, n3,…, ni | n1 ‹n2‹… ‹ni и n1,…, ni 𝜖 𝓝}
Пример:
задан набор 𝑺 числовых данных с элементами, принадлежащими полю действительных чисел R:
𝑺 = { 46, 2, 10, 5, 26, 13, 1 , 4, 52 }
Наша функция сортировки вставкой 𝑓 (𝓝) просто генерирует переупорядочение данных в соответствии с критерием 2 (в порядке возрастания).
Таким образом:
где 𝓝 = 𝑺
𝑓(𝓝) = { 1, 2, 4, 5, 10, 13, 26, 46, 52 }
Сказанное выше верно не только для сортировки вставками. Можно сказать, что это верно для всех алгоритмов, решающих задачу сортировки. Несмотря на то, что все алгоритмы сортировки дают одинаковый конечный результат, их реализации и процессы сортировки значительно различаются. Ниже показано, как конкретно работает сортировка вставкой.
Как работает сортировка вставкой
Процесс сортировки вставки сортировки аналогичен способу сортировки набора карточек в руке.
Сам процесс состоит из четырех этапов:
- Выберите карту
- Сравните эту карту с другими предшествующими ей картами.
- Поместите выбранную карту в соответствующее место
- Перейти к следующей карточке
На примере вышеприведенного набора карточек:
- Выберите шестерку лопат
- Сравните с предыдущей картой (в данном случае с пиковой дамой).
- Переместите шестерку пик на позицию пиковой дамы и наоборот.
- Перейти к следующей карте (пятерка пик), потому что предыдущих карт больше нет
Алгоритм прост, но относительно эффективен (учитывая небольшой размер сортируемых карточек).
Для дальнейшего понимания я реализовал приведенный ниже алгоритм сортировки вставками.
Реализация алгоритма сортировки вставкой на C ++ показана ниже:
Реализация алгоритма сортировки вставкой в Rust показана ниже:
Обе реализации функции сортировки вставкой 𝑓 (𝓝), описанные ранее, принимают несортированный массив данных - в этом случае несортированный массив, содержащий исключительно целочисленные значения и не обслуживающий все поле действительных чисел - и возвращают массив целых чисел, ранее содержащиеся в порядке возрастания.
В обеих программах, указанных выше, соответствующие функции сортировки вставкой вызываются в функциях main () следующим образом:
- InsertSort (набор)
- insert_sort (набор)
Затем массивы несортированных данных сортируются, и возвращается массив отсортированных данных.
Инварианты цикла
Ранее мы определили множество 𝑺 такое, что:
𝑺 = { 46, 2, 10, 5, 26, 13, 1 , 4, 52 }
Чтобы отсортировать указанный выше набор данных в порядке возрастания, как показано в наших реализациях на C ++ и Rust, мы используем переменную i, чтобы отслеживать выбранное значение, которое должно быть помещено в соответствующую позицию сортировки. По мере увеличения i с помощью механизма цикла (в цикле for) можно наблюдать несколько вещей.
- В любой позиции i в 𝑺: 𝑺 [0..i-1] находится в отсортированном порядке.
- В любой позиции i в 𝑺: 𝑺 [i + 1..n] - где n - позиция последнего элемента в наборе - не сортируется.
- Элементы в 𝑺 [i + 1..n] - это элементы, которые изначально находились в 𝑺 [i + 1..n] до сортировки.
Инварианты цикла используются для проверки правильности алгоритма. Чтобы проверить правильность алгоритма с инвариантами цикла, мы должны показать, что три вещи неизменно верны:
- Инициализация: инвариант цикла истинен перед первой итерацией цикла.
- Техническое обслуживание: если инвариант цикла истинен до итерации цикла, он всегда будет истинным до следующей итерации.
- Завершение: цикл должен завершиться, и он должен дать нам полезное свойство, показывающее, что алгоритм верен.
Чтобы проверить правильность алгоритма с инвариантами цикла, мы должны показать, что инициализация, обслуживание и завершение неизменно верны.
Проверка правильности сортировки вставками с инвариантами цикла
Инициализация: мы начинаем с демонстрации истинности инварианта цикла перед первой итерацией цикла. До первой итерации i = 1. Набор 𝑺 [0..i-1] содержит только одно значение в результате позиции i. В результате наличия только одного значения в этом наборе можно сказать, что оно тривиально отсортировано. Следовательно, инвариант цикла верен.
Обслуживание: на следующей итерации цикла i = 2. Набор 𝑺 [0..i-1] в этой точке содержит 2 значения, которые являются значениями в [0] и 𝑺 [ 1].
Таким образом: 𝑺 [0..i-1] = {46, 2}
На этом этапе 2 - это выбранное значение для сравнения с предыдущими элементами набора. 46 оказывается больше 2, и поэтому их позиции меняются местами.
Таким образом: 𝑺 [0..i-1] = {2, 46}
В результате этой операции обмена набор данных 𝑺 [0..i-1] сортируется перед следующей операцией цикла. Следовательно, инвариант цикла сохраняется на всех итерациях цикла.
При желании мы можем дополнительно проверить поддержку в цикле while внутри цикла for.
Прекращение: в этом случае алгоритм завершается. Затем нам нужно убедиться, что алгоритм завершается с правильным результатом. Алгоритм завершается с правильным результатом, если в его конце элементы 𝑺 [0..n] - где n - позиция последнего элемента - находятся в отсортированном порядке и являются теми же элементами, что и в 𝑺 [0..n] ] перед процедурой сортировки. В этом случае:
𝑺 = {46, 2, 10, 5, 26, 13, 1, 4, 52} до сортировки
и 𝑺 = {1, 2, 4, 5, 10, 13, 26, 46, 52} после сортировки.
В результате проверки критериев корректности инициализации, обслуживания и завершения наш алгоритм сортировки вставкой оказался правильным с инвариантами цикла.
