Skip to content

Latest commit

 

History

History
287 lines (249 loc) · 12.5 KB

README.md

File metadata and controls

287 lines (249 loc) · 12.5 KB

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

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

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

let count = 0;

function linearSearch(array, item) {
  for (let i = 0; i < array.length; i++) {
    // count - количество итераций
    count += 1;
    if (array[i] === item) {
      // Возвращаем индекс элемента при нахождении
      return i;
    }
  }
  // Возвращаем null если элемент не найден
  return null;
}

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

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):

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

function recursiveBinarySearch(array, item, start, end) {
  let middle = Math.floor((start + end) / 2);
  count += 1;
  if (item === array[middle]) {
    return middle;
  }
  if (item < array[middle]) {
    // отсеиваем всю правую часть
    return recursiveBinarySearch(array, item, start, middle - 1);
  } else {
    // отсеиваем всю левую часть
    return recursiveBinarySearch(array, item, middle + 1, end);
  }
}

Сортировка выбором(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;
    }

    // Меняем местами элементы
    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):

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):

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

// Факториал - это 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

// Быстрая сортировка(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

// Граф - это некая абстрактная структура данных, предствляющая собой множество
// вершин и набор ребер(т.е соединений между парами вершин).
// Ребра бывают однонаправленными и двунаправленными, то есть если из "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" в точку "B" за минималльное кол-во шагов.
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;
}