Найдите то, что вам нужно, в том порядке, в котором вам это нужно!

Аудитория

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

Мы надеемся покрыть:

  • Алгоритмы кратчайшего пути: алгоритм Дейкстры и алгоритм A*.
  • O(n^2) Алгоритмы сортировки: сортировка вставкой/пузырьком/выбором.
  • O(n log(n)) Алгоритмы сортировки: сортировка слиянием и быстрая сортировка.
  • Топологическая сортировка.
  • Сложные алгоритмы сортировки: пирамидальная сортировка, сортировка по основанию, групповая сортировка и сортировка подсчетом.

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

Аргумент

Алгоритмы кратчайшего пути

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

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

На самом деле существует несколько типов алгоритма кратчайшего пути:

  1. Задача кратчайшего пути из одного источника: кратчайший путь от заданного узла ко всем другим узлам.
  2. Задача кратчайшего пути с одним пунктом назначения: кратчайший путь от всех узлов к заданному узлу.
  3. Проблема кратчайшего пути для всех пар:кратчайшие пути между всеми узлами.

В основном мы собираемся сосредоточиться на типе 1.

Введите алгоритм Джикстры.

Представьте, что у нас есть приведенный ниже график, мы начинаем с A и пытаемся добраться до E.

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

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

Очень важно понимать, что кратчайший путь к узлу v равен кратчайшему маршруту к узлу, соединенному с v, в сочетании с наименьшим расстоянием до самого v. Например, кратчайший путь до D равен минимуму:

  1. Кратчайший путь к B плюс вес ребра B-D
  2. Кратчайший путь к C плюс вес ребра B-C.

Это связано с тем, что B и C являются единственными двумя узлами, подключенными к D, за исключением E, который является нашей целью!

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

Мы повторяем следующие шаги для выполнения Джикстры:

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

Давайте посмотрим, как это может работать в нашем примере.

Мы начинаем с узла A(1) и проверяем B и C (2). Рассчитываем расстояние до начального узла (3), расстояние B равно 2, расстояние C равно 7. Мы обновляем оба из них в таблице, так как они меньше бесконечности (4), и устанавливаем предыдущий узел на A (5). Затем мы добавляем A в наш список посещенных узлов (6). Начнем снова с B (ближайший узел).

Закодируем (полезная статья здесь).

Предостережение к алгоритму Джикстры заключается в том, что он работает только тогда, когда веса положительны. Если какие-то из них отрицательны, нужно использовать алгоритм Беллмана-Форда.

Для самых зорких среди вас вы можете заметить проблему с Djikstra. Он понятия не имеет, приближаетесь ли вы к своей цели, только то, что вы прошли более короткое расстояние. Вы можете пройти небольшое расстояние, но пройти не в ту сторону!

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

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

Мы определили нашу эвристику как количество узлов, которые мы удалили от нашего конечного узла, E. Теперь вместо того, чтобы упорядочивать по пройденному ими расстоянию, мы упорядочиваем по расстоянию + наша эвристика. Это означает, что узлы дальше от конечного узла будут дальше в нашей очереди (в нашем примере у нас не было очереди, вместо этого мы использовали метод getNextNode).

Алгоритмы сортировки по n-квадрату

В предыдущем разделе были рассмотрены наши алгоритмы поиска, теперь мы рассмотрим сортировку.

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

Цель указателя - отметить, где мы отсортировались. В нашем первом проходе мы находим минимум массива. Затем мы меняем его местами с первым элементом и перемещаем указатель. Это делается, поскольку мы знаем все, прежде чем указатель будет отсортирован!

Мы постоянно делаем это с остальной частью массива. Реализация ниже.

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

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

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

Далее мы рассмотрим сортировку вставками. Несмотря на то, что он имеет O(n^2)complexity, в практических ситуациях он немного более эффективен, чем выборка и пузырьковая сортировка.

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

Небольшое замечание: первоначальный порядок списка изменился, чтобы лучше продемонстрировать алгоритм. При сортировке вставками у нас есть указатель, который перемещается по массиву, и временное значение для хранения значения по этому указателю. Мы перемешиваем элементы, превышающие временное значение (но перед указателем), перед помещением временного значения в его массив. законное место.

n-log(n) Алгоритмы сортировки

Алгоритмы следующей сортировки немного сложнее, но и более эффективны. Начнем с сортировки слиянием.

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

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

Имея два отсортированных подмассива, мы можем составить отсортированный массив. Однако как сортировать подмассивы?

Это роль рекурсии. Мы непрерывно разбиваем массив, пока он не будет содержать только один элемент. Один элемент — это отсортированный подмассив! Мы можем вернуться назад, следуя тому же шаблону, который мы определили ранее.

На данный момент самое ясное объяснение — через реализацию.

Теперь переходим к быстрой сортировке. Сортировка слиянием выполняется в O(n log(n)) наихудшем случае, требуя O(n) места. Быстрая сортировка занимает O(n log(n)) среднее время выполнения, а худшее время выполнения составляет O(n^2). Однако он на месте, поэтому мы используем пробел O(1).

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

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

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

Топологическая сортировка

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

Многие реальные проблемы могут быть представлены с помощью ориентированных графов. Популярный пример — предварительные требования к школьному классу (если мне нужно сдать класс A перед классом B). Давайте представим, что у нас есть следующие предварительные условия.

Представьте, что мы хотим пойти в класс E. Для этого нам нужно взять класс C и класс D. Чтобы взять класс C, нам нужно пройти классы A и B. Это дает нам своего рода неявный порядок.

Топологическая сортировка дает нам неуникальное топологическое упорядочение за O(V + E) времени. По сути, это означает, что мы можем выровнять все узлы так, чтобы ребра всегда указывали вправо.

Не все графы будут иметь топологический порядок. Любой граф с направленным циклом не будет иметь его, так как мы не можем начать! У нас должен быть направленный ациклический граф (DAG).

Алгоритм топологической сортировки на верхнем уровне:

  1. Найдите любой непосещенный узел.
  2. Начиная с этого узла, выполните поиск в глубину (DFS) для всех непосещенных узлов.
  3. По мере рекурсивного резервного копирования добавляем текущий узел в порядок в обратном порядке.

Как это работает для нашего примера? Начнем с узла D. Затем мы посещаем E. Поскольку связанных узлов больше нет, мы получаем E-D, затем обращаем его, чтобы добавить D-E к нашему топологическому порядку.

Мы выбираем другой узел B. Затем мы посещаем C, но не идем к E, как мы его видели. Мы получаем B-C, которое затем переворачиваем, чтобы получить C-B, и добавляем к нашему порядку, что дает нам B-C-D-E.

Наконец, мы посещаем единственный непосещенный узел, A, который переворачивается (ничего не делает) и добавляется к началу нашего порядка: A-B-C-D-E.

Наша реализация ниже:

Альтернативой является алгоритм Кана.

Сложные алгоритмы сортировки

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

  • Heapsort: улучшенная сортировка выбором, но в худшем случае O(n log(n)).
  • Сортировка по основанию: подходит для лексикографической сортировки. Сложность равна O(d*(n+b)), d — это количество цифр в заданном списке, n — количество элементов в списке, а b — используемая база, которая обычно равна 10 для десятичного представления. Это имеет больше смысла при рассмотрении алгоритма.
  • Сортировка по сегментам: разделяет несортированные массивы на несколько сегментов. Каждое ведро сортируется с использованием другого алгоритма сортировки или рекурсивно применяется тот же алгоритм ведра. Средняя сложность O(n).
  • Сортировка подсчетом. Метод, основанный на ключах в диапазоне. Это подсчитывает количество объектов, имеющих ключ, и выполняет некоторые арифметические действия для вычисления их положения. Сложность O(n+k), n — количество элементов во входном массиве, k — диапазон ввода.

Поиск и сортировка шпаргалок

* k — количество сегментов в алгоритмах на основе сегментов.
* n — количество элементов массива.
* v,e — количество вершин и ребер в графе.

Заключение

В заключение мы, по общему признанию, несколько случайно, рассмотрели выбор алгоритмов поиска и сортировки!