algorithms-and-data-structures

KO | EN

gitlite — search

#javascript #python #hacktoberfest #typescript #go #rust #deep-learning #docker #windows #kubernetes #vue #pytorch #security #ios

algorithms-and-data-structures

(★ 123)

Javascript algorithms and data structures cheat sheet. Algorithms: linear search, binary search, selection sort, bubble sort, etc.

algorithms-and-data-structures 최신버젼 다운로드

최종 버전 다운로드 (.zip)

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

# Алгоритмы и структуры данных в javascript

![Algs Theory](https://i.imgur.com/Tnh7Krg.png)

### Алгоритм - это последовательность действий, которые решают какую-нибудь задачу. Любой код можно назвать алгоритмом.

![O(n)](https://i.imgur.com/Dr5Lfvb.png)

#### Оценка сложности(O(n)):

- O - о большое, по сути аннотация сложности или скорости алгоритма, на оси это t- время. n - количество операций(всегда указывается максимальное кол-во итерации, то есть наихудший сценарий)
- Некоторые алгоритмы являются эффективнее чем другие.
- Эффективность не всегда равна скорости алгоритма. Некоторые алгоритмы могут быть медленее но более эффективны.

![Diagrams](https://i.imgur.com/FiCIiUh.png)

#### Быстрый пример: Сравнения линейного алгоритма и бинарного на примере обычного массива [0,1,2,3,4,5,6,7,8,9]. Ищем число 7:

В линейном мы идем по каждому элементу - это долго, кол-во операций 10.
В бинарном делим алгоритм на 2 берем последнее число(5) и спрашиваем больше ли оно 7 или нет, итд. Таким образом бинарный алгоритм в разы быстрее и эффективнее.

## Алгоритм линейного поиска в массиве(Linear Search):

```javascript
const array = [1, 4, 5, 8, 5, 1, 2, 7, 5, 2, 11];

let count = 0;

## Бинарный поиск (Binary Search):

```javascript
const array = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15];
let count = 0;

// Реализация с помощью цикла.
// Суть: Находим средний элемент массива, если он равен искомогу, то возращаем его индекс.
// Если больше, то орезаем правую часть, а если меньше, то левую.
function binarySearch(array, item) {
  // Позиция первого элемента
  let start = 0;
  // Позиция последнего элемента
  let end = array.length;
  // Позиция среднего элемента в массиве
  let middle;
  // Флаг, который показывает найден ли элемент в массиве
  let found = false;
  // Позиция найденого элемента. Если элемент не найден, то возвращаем -1
  let position = -1;
  // Цикл работатет до тех пор либо пока не найден элемент, либо пока стартовая и конечная позиция не поровнялись.
  while (found === false && start <= end) {
    // Кол-во итераций
    count += 1;

// Внутри цикла высчитываем позицию центрального элемента
    middle = Math.floor((start + end) / 2);
    // Если он равен искомому элементу, то возвращаем позицию элемента
    if (array[middle] === item) {
      found = true;
      position = middle;
      return position;
    }
    // Если нужный элемент меньше центрального, то тогда нужна левая часть массива, поэтму отсекаем правую.
    if (item < array[middle]) {
      end = middle - 1;
    } else {
      // Если больше, то обрезаем всю левую часть массива
      start = middle + 1;
    }
  }
  return position;
}
```

## Рекурсивный бинарный поиск (Recursive binary Search):

```javascript
// Реализация с помощью рукурсии.
// item - сам элемент, который ищем
// стартовую и конечную позицию передаем через параметры

## Сортировка выбором(Selection Sort):

```javascript
// Сортировка выбором(Selection Sort)

const arr = [
  0, 3, 2, 5, 6, 8, 1, 9, 4, 2, 1, 2, 9, 6, 4, 1, 7, -1, -5, 23, 6, 2, 35, 6, 3,
  32,
];
let count = 0;

// Суть: Есть массив неупорядоченных элементов. Находим в цикле МИНИМАЛЬНЫЙ элемент,
// затем меняем местами с первым элементом, затем опять пробегаемся по массиву и находим минимальное значение,
// но меняем его уже со вторым элементом, затем с 3,4 итд пока не будет отсортирован весь массив.
function selectionSort(array) {
  // Этот цикл просто идет по всем элементам
  for (let i = 0; i < array.length; i++) {
    let indexMin = i;
    // Во вложенном цикле ищется МИНИМАЛЬНЫЙ элемент на данную итерацию
    for (let j = i + 1; j < array.length; j++) {
      if (array[j] < array[indexMin]) {
        indexMin = j;
      }
      count += 1;
    }

// Меняем местами минимальный элемент с current элементом (i)
    let tmp = array[i];
    array[i] = array[indexMin];
    array[indexMin] = tmp;
  }

// Возвращаем отсортированный массив
  return array;
}

// Кол-во итераций 325. Длина массива 26. Таким образом O(1/2*n*n),
// но коэффициенты в оценке сложности алгоритма не учавствуют. Поэтому будет O(n*n)
console.log(selectionSort(arr));
console.log(arr.length);
console.log("count = ", count);
```

## Пузыкрьковая сортировка(Bubble Sort):

```javascript
const arr = [
  0, 3, 2, 5, 6, 8, 23, 9, 4, 2, 1, 2, 9, 6, 4, 1, 7, -1, -5, 23, 6, 2, 35, 6,
  3, 32, 9, 4, 2, 1, 2, 9, 6, 4, 1, 7, -1, -5, 23, 9, 4, 2, 1, 2, 9, 6, 4, 1, 7,
  -1, -5, 23,
];
let count = 0;

// Суть: в двойном цикле пробегаемся по всему массиву и сравниваем попарно лежащие элементы.
// Если следующий элемент массива меньше чем предыдуший, то мы меняем их местами.
// Получается "всплытие" самый большой элемент с каждой итерацией потихоньку всплывает наверх.
function bubbleSort(array) {
  for (let i = 0; i < array.length; i++) {
    for (let j = 0; j < array.length; j++) {
      if (array[j + 1] < array[j]) {
        let tmp = array[j];
        array[j] = array[j + 1];
        array[j + 1] = tmp;
      }
      count += 1;
    }
  }
  return array;
}

console.log("length", arr.length);
console.log(bubbleSort(arr)); // O(n*n)
console.log("count = ", count);
```

## Рекурсия(Recursion):

```javascript
// Рекурсия - это функция, которая вызывает сама себя.
// Рекурсия должна всегда иметь условие, при котором вызов функции прекращается,
// иначе будет переполнение стека вызова.

// Факториал - это n * (n-1) * (n-2) * (n-3) ...
const factorial = (n) => {
  if (n === 1) {
    return 1;
  }
  return n * factorial(n - 1);
};

// Числа фибоначчи -  1,1,2,3,5,8,13,21
const fibonachi = (n) => {
  if (n === 1 || n === 2) {
    return 1;
  }
  return fibonachi(n - 1) + fibonachi(n - 2);
};
```

## Быстрая сортировка(Quick Sort):

![QuickSort](https://i.imgur.com/VIQNhPb.png)

```javascript
// Быстрая сортировка(Quick Sort)

const arr = [
  0, 3, 2, 5, 6, 8, 23, 9, 4, 2, 1, 2, 9, 6, 4, 1, 7, -1, -5, 23, 6, 2, 35, 6,
  3, 32, 9, 4, 2, 1, 2, 9, 6, 4, 1, 7, -1, -5, 23, 9, 4, 2, 1, 2, 9, 6, 4, 1, 7,
  -1, -5, 23,
];
let count = 0;

// Суть: Работает по принципу "Разделяй и властвуй". Мы делим массив на подмассивы и каждый раз рекурсивно.
// Выбираем опорный элемент у каждого массива(его можно выбрать случайно, но чаще всего берут центральный).
// Пробегаемся по массиву и все элементы, которые по значению меньше опорного - добавляем в один массив,
// а все которые больше - в другой. И для каждого из этих массивов выполняется такая же операция.
// Так делается до тех пор, пока  длина массива не станет равна 1.

function quickSort(array) {
  if (array.length <= 1) {
    return array;
  }
  // pivotIndex - опорный индекс элемента, в нашем случае берем центральный (array.length / 2)
  let pivotIndex = Math.floor(array.length / 2);
  // pivot - сам опорный элемент, в нашем случае берем центральный
  let pivot = array[pivotIndex];
  // массив с числами, которые меньше чем опорные
  let less = [];
  // массив с числами, которые больше чем опорные
  let greater = [];

// Проходимся по всему массиву и наполняем массивы less и greater
  for (let i = 0; i < array.length; i++) {
    count += 1;
    if (i === pivotIndex) continue;
    if (array[i] < pivot) {
      less.push(array[i]);
    } else {
      greater.push(array[i]);
    }
  }

// Проделывем ту же самую операцию с двумя след. массивами
  return [...quickSort(less), pivot, ...quickSort(greater)];
}
```

## Поиск в ширину в графе(Breadth First Search):

![BreadthFirstSearch](https://i.imgur.com/SxOxCXk.png)
![Queue](https://i.imgur.com/IMM1k7M.png)

```javascript
// Граф - это некая абстрактная структура данных, предствляющая собой множество
// вершин и набор ребер(т.е соединений между парами вершин).
// Ребра бывают однонаправленными и двунаправленными, то есть если из "A" можно попасть только в "B" - это однонаправленность.
// А если можно из "A" в "B" и из "B" в "A" - - это двунаправленность.

const graph = {};
graph.a = ["b", "c"];
graph.b = ["f"];
graph.c = ["d", "e"];
graph.d = ["f"];
graph.e = ["f"];
graph.f = ["g"];

// Задача: Найти существует ли путь из точки "A" в точку "G" за минималльное кол-во шагов.

// Этот алгоритм:
// 1) Решает задачу поиска пути в графу, существует ли такой путь
// 2) Находит путь за минимальное кол-во шагов
function breadthSearch(graph, start, end) {
  // Очередь(queue) - структура данных состоящая из каких-то элементов.
  // Основной принцип заключается в том, что элементы всегда добавляются в конец структуры, а
  // извлекаются из ее начала. Принцип как в очереди в жизни: кто первым пришел на кассу, тот из
  // нее первый и уходит. Такой принцип называется FIFO - first in first out.
  let queue = [];
  //   В очередь сразу добавляем стартовую вершину(start, в данном случае "a")
  queue.push(start);
  //   Крутим цикл while пока в очереди есть хотя бы один элемент
  while (queue.length > 0) {
    // Из начала очереди достаем текущую вершину
    const current = queue.shift();
    // Если по текущей вершине в графе ничего не находится, то присваиваем этой вершине пустой массив
    if (!graph[current]) {
      graph[current] = [];
    }
    // Если в графе по текущей вершине массив содержит конечную точку, то мы завершаем выполнение
    // программы и возвращаем true. То есть на данном этапе мы обошли весь граф и пришли
    // к пункту назначения.
    if (graph[current].includes(end)) {
      return true;
    } else {
      // Если это условие не отработало, то мы должны добавить в очередь новые вершины.
      //   Поэтому разворачиваем то, что уже находится в очереди в массив и в конец разворачиваем массив
      //   который лежит в графе по текущей вершине.
      queue = [...queue, ...graph[current]];
    }
  }
  return false;
}
```

## Алгоритм дейкстры для поиска кратчайшего пути в графе (Dijkstra's algorithm):

![Dijkstra's algorithm](https://i.imgur.com/WNXt8MD.png)
![Dijkstra's algorithm](https://i.imgur.com/VMAMtbw.png)

```javascript
// Алгоритм дейкстры для поиска кратчайшего пути в графе (Dijkstra's algorithm)

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

// Суть: За стартовую точку принимаем A, за конечную G. Состовляется табличка, в которую на первом этапе
// записываются значения тех вершин, в которые мы можем попасть из стартовой точки. Все остальные
// вершины являются не достижимыми и мы их помечаем знаком бесконечности. На втором этапе мы помечаем эти вершины
// как уже рассмотренные. На третьем этапе мы рассматриваем вершины, в которые мы можем попасть из точек B и C
// и в таблицу записываем значение от точки A, до точек, которые мы достигаем из вершин B и C. Потом опять помечаем эти точки
// как уже рассмотренные. На следующем этапе мы достигаем точки G, но у нас происходит перерасчет, мы находим путь до точки F,
// которая оказывается короче и перезаписываем значение в таблице и на следующем этапе мы проделаем все тоже самое и находим
// самый оптимальный путь и узнаем, что из точки A в точку G мы можем добраться за 5 условных единиц.

// 3) --------------------------------------------------
  // Получаем объект с минимальной стоимостью
  let node = findNodeLowestCost(costs, processed);
  // Делаем цикл while, в котором будем крутиться до тех пор, пока эта нода не пустая.
  //

while (node) {
    // На кажой итерации получаем стоимость текущей вершины
    const cost = costs[node];
    // Те узлы в которые мы можем попасть из этой вершины мы присваиваем в neighbors
    neighbors = graph[node];
    Object.keys(neighbors).forEach((neighbor) => {
      // Высчитываем новую стоимость
      let newCost = cost + neighbors[neighbor];
      //Перезаписываем в таблице значение если новая стоимость меньше
      if (newCost < costs[neighbor]) {
        costs[neighbor] = newCost;
      }
    });
    //  Добавляем вершину в массив уже обработанных вершин, после чего при поиске вершин с минимальной
    //  стоимостью эта вершина уже учитываться не будет.
    processed.push(node);
    // И ищем новую вершину.
    node = findNodeLowestCost(costs, processed);
  }
  // Возврашаем объект, который хранит  самые кратчайшие пути.
  return costs;
}

// 2) --------------------------------------------------
// На этом этапе необходимо найти вершину, в которую мы можем попасть из точки A
// и путь в которую самый короткий. Название ф-ии "Найти узел с минимальной стоимостью"
function findNodeLowestCost(costs, processed) {
  // lowestCost - будет хранить минимальное значение, по умолчанию 100000000
  let lowestCost = 100000000;
  // lowestNode - нода, которую мы будем возвращать с минимальным значением
  let lowestNode;
  // Теперь необходимо проитерироваться по ключам объекта в котором мы храним стоимость путей.
  Object.keys(costs).forEach((node) => {
    // Получим стоимость текущей ноды
    let cost = costs[node];
    // Если стоимость, которую мы получили меньше чем минимальная стоимость, которую мы определили в самом начале
    // и вершина которую мы рассматриваем на текущей итерации не находится в массиве обработанных вершин.
    // То есть мы сравниваем стоимость - если она меншьше и если узел еще не обработан, то мы обновляем переменные.
    if (cost < lowestCost && !processed.includes(node)) {
      // Если условие выполнилось, то мы нашли объект у которого путь короче.
      // Соотвественно мы перезаписываем минимальную стоимость на  ту, которую мы сейчас нашли на этой итерации
      // и заменяем ноду.
      lowestCost = cost;
      lowestNode = node;
    }
  });

//   Возврашаем вершину с минимальной стоимостью.
  return lowestNode;
}

console.log(shortPath(graph, "a", "g"));
```

## Stack (задача на обход всех узлов в дереве):

![Stack](https://i.imgur.com/M4QHSog.png)

```javascript
// Задача посчитать сумму значений всех узлов
// v - значение, с - потомки
// Если у узла нету потомков, то его называют "листом"

const tree = [
  {
    v: 5,
    c: [
      {
        v: 5,
      },
      {
        v: 10,
        c: [
          {
            v: 11,
          },
        ],
      },
      {
        v: 11,
        c: [
          {
            v: 12,
            c: [
              {
                v: 5,
              },
            ],
          },
        ],
      },
    ],
  },
  {
    v: 5,
    c: [
      {
        v: 7,
      },
      {
        v: 12,
        c: [
          {
            v: 11,
          },
        ],
      },
      {
        v: 14,
      },
    ],
  },
];

// Суть: для реализации с помощью итерации нужна структура данных - СТЕК.
// Стек похож на очередь, но работает по другому. Элементы всегда добавляются в конец структуры и извлекаются
// также из конца. В очереди добавляем в конец, а извлекаем из начала, то в стеке мы добавляем и извлекаем с конца.

function treeSum(tree) {
  if (!tree.length) {
    return 0;
  }

let sum = 0;
  // Создаем структуру данных стек, в которую будем записывать узлы.
  let stack = [];

// Добавляем вершины дерева в стек
  tree.forEach((node) => stack.push(node));

while (stack.length) {
    let node = stack.pop();
    sum += node.v;
    if (node.c) {
      node.c.forEach((n) => stack.push(n));
    }
  }

return sum;
}

console.log(treeSum(tree));

// Рекурсивный вариант

function recursiveTreeSum(tree) {
  let sum = 0;

tree.forEach((node) => {
    sum += node.v;

if (!node.c) {
      return node.v;
    }

sum += recursiveTreeSum(node.c);
  });

return sum;
}

console.log(recursiveTreeSum(tree));
```

## Алгоритм кеширования:

```javascript
// Алгоритм кеширования данных во избижании повторных вычеслений

// cashFunction - ф-ия которая кеширует внутри себя результат вычесления другой ф-ии fn
function cashFunction(fn) {
  // Объект, который хранит по ключу результат кеширования, ключем будет параметр n который мы передаем в fn
  const cash = {};

return (n) => {
    if (cash[n]) {
      console.log("Выведено из кеша: ", cash[n]);

return cash[n];
    }

let result = fn(n);

cash[n] = result;

console.log("Выведено не из кеша: ", cash[n]);

return result;
  };
}

// Допустим ф-ия факториала очень тяжелая, а мы не хотим трать лишние ресурсы, поэтому кешируем вычесления и выдаем их.
function factorial(n) {
  let result = 1;
  while (n != 1) {
    result *= n;
    n -= 1;
  }

return result;
}

const cashFactorial = cashFunction(factorial);

cashFactorial(5);
cashFactorial(4);
cashFactorial(3);
cashFactorial(4);
cashFactorial(5);
cashFactorial(1);
```

## Связанный список (Linked List):

![Linked List](https://i.imgur.com/G1dtbmP.png)

```javascript
// Структура данных: Связанный список (Linked List)
// Связанный список - каждый отдельно взятый элемент списка занимает отдельное место  в памяти.
// Связанность списка происходит за счет того, что каждый пердыдущий элемент хранит ссылку на следующий элемент,
// который лежит в списке. Плюс такого подхода в том, что мы можем мгновенно добавлять элементы в конец или в начало
// списка. А минус в том, что чтобы получить какой-то элемент - нам с самого начала списка надо итерироваться и сравнивать.
// Таким образом список больше подходит в том случае если мы редко обращаемся к каким-то данным и часто его дополняем.

// Суть: каждый предыдущий элемент ссылается на последующий

class LinkedList {
  constructor() {
    // Размер самого списка
    this.size = 0;
    //Корневой элемент
    this.root = null;
  }

add(value) {
    if (this.size === 0) {
      // Если размер равен 0 тогда создаем корневой элемент
      this.root = new Node(value);
      this.size += 1;
      // Прекращаем выполнение ф-ии
      return true;
    }

let node = this.root;
    // Крутимся в цикле до тех пор пока в ноде есть следующий жоемент
    while (node.next) {
      // Присваеваем следующий элемент переменной node
      node = node.next;
    }
    // После того как дошли до последнего элемента в списке, создаем новую ноду
    let newNode = new Node(value);
    // Указываем ссылку на новую ноду последнему элементу
    node.next = newNode;
    this.size += 1;
  }

getSize() {
    return this.size;
  }

print() {
    let result = [];
    let node = this.root;
    while (node) {
      result.push(node.value);
      node = node.next;
    }
    console.log(result);
  }
}

// Класс для отдельного узла
class Node {
  constructor(value) {
    this.value = value;
    // Будет хранить ссылку на следующий элемент в списке
    this.next = null;
  }
}

const list = new LinkedList();
list.add(5);
list.add(3);
list.add(2);
list.add(5);
list.add(7);

list.print();
```

## Бинарное дерево (Binary Tree):

![Binary Tree](https://i.imgur.com/3vHvdE3.png)

```javascript
// Структура данных: Бинарное дерево (Binary Tree)

// Бинарное дерево - это структура данных, где каждый узел  также является деревом, то есть структура рекурсивная,
// и основная суть в том, что у каждого узла может быть 2 потомка.
// Добавляются эти узлы тоже особым способом: если добавляемое в дерево значение меньше по значению чем текущий угол,
// то значение уходит в левое поддерево, если больше, то уходит в правое. И так получается, что правая часть поддерева выстраивается с большими
// значениями, а левая с меньшими. И это дерево называется бинарным деревом поиска, поскольку аналогично бинарному алгоритму поиска
// здесь можно находить данные за логарифмическое время.

class BinaryTree {
  constructor() {
    this.root = null;
  }

add(value) {
    // Если корневой элемент не существует, тогда необходимо его проинициализировать.
    if (!this.root) {
      this.root = new TreeNode(value);
    } else {
      let node = this.root;
      let newNode = new TreeNode(value);

//   Крутимся пока node не равен пустому значанию
      while (node) {
        //  Если значение больше чем значение ноды, то мы уйдем в правое поддерево, в обратном случае уйдем в левое поддерево
        if (value > node.value) {
          // Если правого поддерева нет, то остановим цикл
          if (!node.right) {
            break;
          }
          node = node.right;
        } else {
          if (!node.left) {
            break;
          }
          node = node.left;
        }
      }

//   Таким образом после цикла мы имеем ноду которая находится в самом низу цикла
      // Опять делаем проверку значения
      if (value > node.value) {
        node.right = newNode;
      } else {
        node.left = newNode;
      }
    }
  }

//  Рекурсивная ф-ия print
  print(root = this.root) {
    // Любая рекурсивная ф-ия должна иметь условия выхода из этой рекурсии
    if (!root) {
      return true;
    }
    console.log(root.value);
    this.print(root.left);
    this.print(root.right);
  }
}

// Создаем узела
class TreeNode {
  constructor(value) {
    this.value = value;
    // Создаем ссылку на элемент кторый находится в левой части дерева
    this.left = null;
    // Создаем ссылку на элемент кторый находится в правой части дерева
    this.right = null;
  }
}

const tree = new BinaryTree();
tree.add(5);
tree.add(2);
tree.add(6);
tree.add(2);
tree.add(1);
tree.print();
```

## Бинарное дерево (Binary Tree):

![Map, Set](https://i.imgur.com/7rFB52r.png)

```javascript
// Структура данных: Map. Cловарь, карта или map, называют по разному. Хранит в себе пары ключ-значение. По сути обычный объект в js
// уже является map.Основное преимущество структуры в том, что мы можем за константное(мгновенное) время добавлять объекты в структуру
// и извлекать.

// Структура данных: Set. Set - это некое множество, своего рода массив, который хранит в себе только уникальные значения.
```

algorithms-and-data-structures

algorithms-and-data-structures 최신버젼 다운로드

오늘의 추천 프로젝트

Was this content helpful?

Recent Feedback

algorithms-and-data-structures

algorithms-and-data-structures 최신버젼 다운로드

오늘의 추천 프로젝트

Was this content helpful?

Recent Feedback

Download README