В этой статье я хотел бы представить свой топ-10 алгоритмов, которые могут помочь вам в работе. Бонусом покажу на примерах, как ими пользоваться.
Сам список включает в себя следующие алгоритмы:
QuickSort - алгоритм разделения и покорения, который рекурсивно разбивает массив на более мелкие подмассивы и сортирует их.
MergeSort - алгоритм "разделяй и властвуй", который рекурсивно делит массив пополам, сортирует половинки, а затем объединяет их обратно.
Бинарный поиск - алгоритм поиска, который многократно делит интервал поиска пополам, ища определенное значение в отсортированном массиве.
Поиск в глубину (DFS)- алгоритм обхода графа, который исследует как можно дальше по каждой ветви, прежде чем вернуться назад.
Breadth-first Search (BFS) - алгоритм обхода графа, который исследует все вершины графа или все узлы дерева уровень за уровнем.
Динамическое программирование - метод решения проблем путем разбиения их на более мелкие подпроблемы и хранения решений этих подпроблем, чтобы избежать лишней работы.
Алгоритм Беллмана-Форда - алгоритм кратчайшего пути с одним источником, который также может обнаруживать отрицательные циклы в графе.
Алгоритм Дейкстры- алгоритм кратчайшего пути с одним источником, который работает путем многократного ослабления оценок расстояния между вершинами.
Алгоритм поиска A* - алгоритм поиска, который использует эвристику для направления поиска и обычно используется для поиска пути и решения задач обхода графа.
Knapsack Problem - задача комбинаторной оптимизации, целью которой является максимизация общей стоимости предметов в рюкзаке без превышения его вместимости.
Для примерах реализации я буду использовать Typescript, так как это ЯП с сильной типизацией, но в тоже время достаточно простой для понимания.
Заметка: все вышеперечисленные алгоритмы реализованы с помощью typescript и могут быть найдены в менеджере пакетов npm.
1. Пример алгоритма quicksort, реализованного на TypeScript:
function quickSort(arr: number[], left: number, right: number): void {
let pivot: number;
let partitionIndex: number;
if(left < right) {
pivot = right;
partitionIndex = partition(arr, pivot, left, right);
//sort left and right
quickSort(arr, left, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, right);
}
}
function partition(arr: number[], pivot: number, left: number, right: number): number {
let pivotValue = arr[pivot];
let partitionIndex = left;
for(let i = left; i < right; i++) {
if(arr[i] < pivotValue) {
swap(arr, i, partitionIndex);
partitionIndex++;
}
}
swap(arr, right, partitionIndex);
return partitionIndex;
}
function swap(arr: number[], i: number, j: number): void {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
let numbers = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0];
quickSort(numbers, 0, numbers.length - 1);
console.log(numbers);
Эта реализация quicksort принимает массив чисел, а также левый и правый индексы части массива, который нужно отсортировать, в качестве входных данных. Она использует pivot элемент для разбиения массива на два меньших подмассива и рекурсивно сортирует левый и правый разделы. Используется вспомогательная функция partition для перестановки элементов массива таким образом, чтобы все элементы меньше pivot находились слева от него, а все элементы больше pivot - справа. Функция swap используется для замены элементов в массиве местами.
Стоит отметить, что значение pivot может быть выбрано по-разному, здесь в качестве pivot выбран последний элемент, но это может быть любой случайный элемент или медианное значение массива для лучшей производительности.
2. Вот пример алгоритма MergeSort, реализованного на TypeScript:
function mergeSort(arr: number[]): number[] {
if (arr.length === 1) {
return arr;
}
const middle = Math.floor(arr.length / 2);
const left = arr.slice(0, middle);
const right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left: number[], right: number[]): number[] {
let result = [], leftIndex = 0, rightIndex = 0;
while (leftIndex < left.length && rightIndex < right.length) {
if (left[leftIndex] < right[rightIndex]) {
result.push(left[leftIndex]);
leftIndex++;
} else {
result.push(right[rightIndex]);
rightIndex++;
}
}
return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}
let numbers = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0];
let sortedNumbers = mergeSort(numbers);
console.log(sortedNumbers);
Эта реализация функции merge sort принимает массив чисел в качестве входных данных и возвращает новый отсортированный массив. Функция mergeSort использует подход "разделяй и властвуй", рекурсивно разделяя входной массив пополам и сортируя два получившихся подмассива. Функция merge используется для объединения двух подмассивов в отсортированном порядке.
Она работает путем разделения входного массива на две половины, рекурсивной сортировки каждой половины, а затем объединения отсортированных половин вместе с помощью функции merge, которая сравнивает элементы в левом и правом массивах и добавляет наименьший элемент в результирующий массив.
Стоит отметить, что merge sort является стабильным алгоритмом сортировки, то есть элементы с одинаковым значением сохраняют свой относительный порядок в отсортированном результате, а его временная сложность составляет O(n log n).
3. Вот пример алгоритма двоичного поиска, реализованного на TypeScript:
function binarySearch(arr: number[], x: number): number {
let start = 0;
let end = arr.length - 1;
while (start <= end) {
let middle = Math.floor((start + end) / 2);
if (arr[middle] === x) {
return middle;
} else if (arr[middle] < x) {
start = middle + 1;
} else {
end = middle - 1;
}
}
return -1;
}
let numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
let index = binarySearch(numbers, 6);
console.log(index);
Эта реализация двоичного поиска принимает на вход массив чисел и искомое значение. Она использует цикл while для многократного деления интервала поиска пополам. Цикл продолжается до тех пор, пока значение не будет найдено или пока интервал поиска не станет пустым. Середина интервала вычисляется путем взятия среднего значения начального и конечного индексов, и значение элемента по этому индексу сравнивается с искомым значением. Если оно равно, возвращается индекс элемента. Если значение элемента меньше значения поиска, поиск продолжается в правой половине интервала. Если элемент больше значения поиска, то поиск продолжается в левой половине интервала.
Стоит отметить, что этот алгоритм требует сортировки входного массива и имеет временную сложность O(log n), что делает его эффективным при поиске в больших массивах.
Кроме того, это базовая реализация двоичного поиска, и ее можно улучшить, позаботившись о крайних случаях, например, когда элемент не найден в массиве. Функция может возвращать -1 или любое другое конкретное значение, чтобы показать, что элемент не найден в массиве.
4. Вот пример алгоритма поиска в глубину (DFS), реализованного в TypeScript:
class Graph {
constructor(private numOfVertices: number) {
this.adjList = new Map<number, number[]>();
}
private adjList: Map<number, number[]>;
addVertex(v: number) {
this.adjList.set(v, []);
}
addEdge(v: number, w: number) {
this.adjList.get(v).push(w);
this.adjList.get(w).push(v);
}
dfs(vertex: number, visited: boolean[]) {
visited[vertex] = true;
console.log(vertex);
let neighbours = this.adjList.get(vertex);
for (let i = 0; i < neighbours.length; i++) {
let neighbour = neighbours[i];
if (!visited[neighbour]) {
this.dfs(neighbour, visited);
}
}
}
}
let g = new Graph(6);
let vertices = [0, 1, 2, 3, 4, 5];
for (let i = 0; i < vertices.length; i++) {
g.addVertex(vertices[i]);
}
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(2, 4);
g.addEdge(3, 5);
let visited = new Array(6).fill(false);
console.log('DFS:');
g.dfs(0, visited);
Данная реализация DFS использует представление графа в виде списка смежности, где каждая вершина представлена ключом в карте, а ее значение - массив соседних вершин.
Функция dfs начинает с пометки текущей вершины как посещенной, а затем рекурсивно вызывает себя для каждой не посещенной соседней вершины. Базовый случай рекурсии — когда все соседи текущей вершины были посещены.
Стоит отметить, что в данном примере показан обход DFS, начиная с вершины 0, но он может быть запущен с любой вершины, и для реализации DFS полезно использовать стековую структуру данных.
Кроме того, это базовая реализация DFS, и она может быть использована для различных целей, таких как проверка наличия цикла в графе, поиск сильно связанных компонентов и решение таких задач, как обход лабиринта или поиск пути между двумя вершинами.
В первой части мы написали и разобрали 4 алгоритма. Далее реализуем более сложные и интересные проблемы, такие как Knapsack Problem, например.
Спасибо за прочтение. Надеюсь, мой пост был полезным! Жду ваших комментариев и пожеланий 😎