Алгоритмы в JavaScript

Вступление

Прочитав великолепную книгу «Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих» Адитья Бхаргава, столкнулся с тем, что примеры кода в книге написаны на Python. Справедливо ли это по отношению к JavaScript? Конечно же нет :) И в этом репозитории мы это исправим.

Кому пригодится этот репозиторий

Всем кто только начинает обучаться программированию или готовиться к собеседованию (слышал, что вопросы про алгоритмы звучать на интервью с завидной частотой).

---

Что такое алгоритм

Алгори́тм (лат. algorithmi — от имени среднеазиатского математика Аль-Хорезми) — конечная совокупность точно заданных правил решения некоторого класса задач или набор инструкций, описывающих порядок действий исполнителя для решения определённой задачи.

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

Материал из Википедии — свободной энциклопедии

«О-большое (Big O)»

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

Например, для проверки списка размером n бинарному поиску потребуется log n операций или O(log n).

Логарифмы

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

Возведение в степень	Логарифм
102 = 100	log10100 = 2
103 = 1000	log101000 = 3
23 = 8	log28 = 3
24 = 16	log216 = 4
25 = 32	log232 = 5

Линейный поиск

Описание

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

Скорость выполнения О(n), или линейное время.

Пример кода

Бинарный поиск

Описание

Бинарный поиск — простой, интуитивно понятный и эффективный алгоритм поиска.
Внимание: работает только с отсортированными массивами.

Порядок работы:

1. Определение значения элемента в середине структуры данных. Полученное значение сравнивается с ключом.
2. Если ключ меньше значения середины, то поиск осуществляется в первой половине элементов, иначе — во второй.
3. Поиск сводится к тому, что вновь определяется значение серединного элемента в выбранной половине и сравнивается с ключом.
4. Процесс продолжается до тех пор, пока не будет найден элемент со значением ключа или не станет пустым интервал для поиска.

Скорость выполнения O(log n), или логарифмическое время.

Пример кода

Сортировка выбором

Описание

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

Алгоритмы сортировки очень полезны, но работают медленно

Могут быть полезны в сортировки, например:

1. Имён в телефонной книге
2. Дат путешествий
3. Сообщений e-mail (от новых к старым)

Скорость выполнения O( n_х_n), или O(log n²).

Пример кода

const selectionSort = arr => {
    for (let i = 0, l = arr.length, k = l - 1; i < k; i++) {
        let indexMin = i;
        for (let j = i + 1; j < l; j++) {
            if (arr[indexMin] > arr[j]) {
                indexMin = j;
            }
        }
        if (indexMin !== i) {
            [arr[i], arr[indexMin]] = [arr[indexMin], arr[i]];
        }
    }
    return arr;
};