# Алгоритми JavaScript та структури даних [](https://github.com/trekhleb/javascript-algorithms/actions?query=workflow%3ACI+branch%3Amaster) [](https://codecov.io/gh/trekhleb/javascript-algorithms) Даний репозиторій приклади багатьох популярних алгоритмів та структур даних на основі JavaScript. Кожен алгоритм та структура даних має свій окремий README-файл із відповідними поясненнями та посиланнями для подальшого вивчення (включаючи посилання на відео на YouTube). _Вивчення матеріалу на інших мовах:_ [_English_](README.md), [_简体中文_](README.zh-CN.md), [_繁體中文_](README.zh-TW.md), [_한국어_](README.ko-KR.md), [_日本語_](README.ja-JP.md), [_Polski_](README.pl-PL.md), [_Français_](README.fr-FR.md), [_Español_](README.es-ES.md), [_Português_](README.pt-BR.md), [_Русский_](README.ru-RU.md), [_Türk_](README.tr-TR.md), [_Italiana_](README.it-IT.md), [_Bahasa Indonesia_](README.id-ID.md), [_Arabic_](README.ar-AR.md), [_Tiếng Việt_](README.vi-VN.md), [_Deutsch_](README.de-DE.md), [_Uzbek_](README.uz-UZ.md) [_עברית_](README.he-IL.md) *☝ Зверніть увагу! Даний проект призначений лише для навчальних та дослідницьких цілей, і він **не** призначений для виробництва (продакшн).* ## Структури даних Структура даних (в програмуванні) - це спосіб організації даних в комп'ютерах. Часто разом зі структурою даних пов'язується і специфічний перелік операцій, що можуть бути виконаними над даними, організованими в таку структуру. Точніше, структура даних - це сукупність даних цінності, взаємозв'язки між ними та функції або операції, до яких можна застосувати дані. `B` - Початківець, `A` - Просунутий рівень * `B` [Зв'язаний список](src/data-structures/linked-list) * `B` [Двобічно зв'язаний список](src/data-structures/doubly-linked-list) * `B` [Черга](src/data-structures/queue) * `B` [Стек](src/data-structures/stack) * `B` [Геш-таблиця](src/data-structures/hash-table) * `B` [Купа, стіс або піраміда](src/data-structures/heap) - max and min heap versions * `B` [Черга з пріоритетом](src/data-structures/priority-queue) * `A` [Префіксне дерево](src/data-structures/trie) * `A` [Дерево](src/data-structures/tree) * `A` [Двійкове дерево пошуку](src/data-structures/tree/binary-search-tree) * `A` [АВЛ-дерево](src/data-structures/tree/avl-tree) * `A` [Червоно-чорне дерево](src/data-structures/tree/red-black-tree) * `A` [Дерево відрізків](src/data-structures/tree/segment-tree) - with min/max/sum range queries examples * `A` [Дерево Фенвіка](src/data-structures/tree/fenwick-tree) (Binary Indexed Tree) * `A` [Граф (абстрактний тип даних)](src/data-structures/graph) (both directed and undirected) * `A` [Система неперетинних множин](src/data-structures/disjoint-set) * `A` [Фільтр Блума](src/data-structures/bloom-filter) ## Алгоритми Алгоритм - це однозначна специфікація способу вирішення класу задач. Це набір правил, які точно визначають послідовність операцій. `B` - Початківець, `A` - Просунутий рівень ### Алгоритми за тематикою * **Математика** * `B` [Бітова маніпуляція](src/algorithms/math/bits) - встановити / отримати / оновити / очистити біти, множення / ділення на два, робити від’ємними тощо * `B` [Факторіал](src/algorithms/math/factorial) * `B` [Послідовність Фібоначчі](src/algorithms/math/fibonacci) - класична та закриті версії * `B` [Основні фактори](src/algorithms/math/prime-factors) - пошук простих множників і підрахунок їх за допомогою теореми Харді-Рамануджана * `B` [Тест простоти](src/algorithms/math/primality-test) (метод пробного поділу) * `B` [Алгоритм Евкліда](src/algorithms/math/euclidean-algorithm) - метод обчислення найбільшого спільного дільника (НСД) * `B` [Найменше спільне кратне](src/algorithms/math/least-common-multiple) (НСК) * `B` [Решето Ератосфена](src/algorithms/math/sieve-of-eratosthenes) - алгоритм знаходження всіх простих чисел менших деякого цілого числа *n* * `B` [Піднесення до степеня](src/algorithms/math/is-power-of-two) - перевірити, чи є число ступенем двох (просте та побітове рішення) * `B` [Трикутник Паскаля](src/algorithms/math/pascal-triangle) * `B` [Комплексне число](src/algorithms/math/complex-number) - комплексні числа та основні операції з ними * `B` [Радіани & Градуси](src/algorithms/math/radian) - перетворення радіанів у градуси та навпаки * `B` [Швидке піднесення до степеня](src/algorithms/math/fast-powering) * `B` [Схема Горнера](src/algorithms/math/horner-method) - поліноміальна оцінка * `A` [Розбиття числа](src/algorithms/math/integer-partition) * `A` [Метод дотичних (метод Ньютона)](src/algorithms/math/square-root) - метод наближеного знаходження кореня дійсного рівняння * `A` [Алгоритм Лю Хуея](src/algorithms/math/liu-hui) - розрахунок числа π з заданою точністю методом вписаних правильних багатокутників * `A` [Дискретне перетворення Фур'є](src/algorithms/math/fourier-transform) - розкладання тимчасової функції (сигналу) на частотні складові * **Множина** * `B` [Декартів добуток множин](src/algorithms/sets/cartesian-product) - множина усіх можливих впорядкованих пар * `B` [Тасування Фішера - Єйтса](src/algorithms/sets/fisher-yates) - створення випадкових перестановок кінцевого безлічі * `A` [Булеан](src/algorithms/sets/power-set) - множина всіх підмножин даної множини (бітові та зворотні рішення) * `A` [Перестановка](src/algorithms/sets/permutations) (з повтореннями та без) * `A` [Комбінації](src/algorithms/sets/combinations) (з повтореннями та без) * `A` [Пошук найдовшої спільної підпослідовності](src/algorithms/sets/longest-common-subsequence) * `A` [Завдання пошуку найбільшою збільшується підпослідовності](src/algorithms/sets/longest-increasing-subsequence) * `A` [Найменша загальна супер-послідовність](src/algorithms/sets/shortest-common-supersequence) * `A` [Задача пакування рюкзака](src/algorithms/sets/knapsack-problem) - приклади "0/1" та "Необмежений" * `A` [Максимальний підмасив](src/algorithms/sets/maximum-subarray) - метод «Грубої сили» та алгоритм Кадана * `A` [Комбінована сума](src/algorithms/sets/combination-sum) - знайти всі комбінації, що утворюють конкретну суму * **Алгоритми роботи з рядками** * `B` [Відстань Геммінга](src/algorithms/string/hamming-distance) - число позицій, у яких відповідні цифри двох двійкових слів однакової довжини різні * `A` [Відстань Левенштейна](src/algorithms/string/levenshtein-distance) - міра відмінності двох послідовностей символів (рядків) * `A` [Алгоритм Кнута — Морріса — Пратта](src/algorithms/string/knuth-morris-pratt) пошук підрядків (узгодження шаблонів) * `A` [Z-функція](src/algorithms/string/z-algorithm) - пошук підрядків (зіставлення зразків) * `A` [Алгоритм Рабіна — Карпа](src/algorithms/string/rabin-karp) - алгоритм пошуку рядка * `A` [Найбільший загальний підрядок](src/algorithms/string/longest-common-substring) * `A` [Підбирання регулярного виразу](src/algorithms/string/regular-expression-matching) * **Алгоритми пошуку** * `B` [Лінійний пошук](src/algorithms/search/linear-search) * `B` [Пошук блоків](src/algorithms/search/jump-search) - пошук у відсортованому масиві * `B` [Двійковий пошук](src/algorithms/search/binary-search) - знаходження заданого значення у впорядкованому масиві * `B` [Інтерполяційний алгоритм пошуку](src/algorithms/search/interpolation-search) - алгоритм для пошуку за заданим ключем в індексованому масиві, який впорядкований за значенням ключів * **Алгоритми сортування** * `B` [Сортування бульбашкою](src/algorithms/sorting/bubble-sort) * `B` [Сортування вибором](src/algorithms/sorting/selection-sort) * `B` [Сортування включенням](src/algorithms/sorting/insertion-sort) * `B` [Пірамідальне сортування](src/algorithms/sorting/heap-sort) * `B` [Сортування злиттям](src/algorithms/sorting/merge-sort) * `B` [Швидке сортування](src/algorithms/sorting/quick-sort) * `B` [Сортування Шелла](src/algorithms/sorting/shell-sort) * `B` [Сортування підрахунком](src/algorithms/sorting/counting-sort) * `B` [Сортування за розрядами](src/algorithms/sorting/radix-sort) * **Зв’язані списки** * `B` [Прямий обхід](src/algorithms/linked-list/traversal) * `B` [Зворотний обхід](src/algorithms/linked-list/reverse-traversal) * **Дерева** * `B` [Пошук у глибину](src/algorithms/tree/depth-first-search) * `B` [Пошук у ширину](src/algorithms/tree/breadth-first-search) * **Графи** * `B` [Пошук у глибину](src/algorithms/graph/depth-first-search) * `B` [Пошук у ширину](src/algorithms/graph/breadth-first-search) * `B` [Алгоритм Крускала](src/algorithms/graph/kruskal) - алгоритм побудови мінімального кістякового дерева зваженого неорієнтовного графа * `A` [Алгоритм Дейкстри](src/algorithms/graph/dijkstra) - знаходження найкоротшого шляху від однієї вершини графа до всіх інших вершин * `A` [Алгоритм Беллмана — Форда](src/algorithms/graph/bellman-ford) - алгоритм пошуку найкоротшого шляху в зваженому графі * `A` [Алгоритм Флойда — Воршелла](src/algorithms/graph/floyd-warshall) - знаходження найкоротшого шляху в зваженому графі з додатними або від'ємними вагами ребер (але без від'ємнозначних циклів) * `A` [Циклічний граф](src/algorithms/graph/detect-cycle) - граф, що складається з єдиного циклу, або, іншими словами, деякого числа вершин, з'єднаних замкнутим ланцюгом. * `A` [Алгоритм Прима](src/algorithms/graph/prim) - жадібний алгоритм побудови мінімального кістякового дерева зваженого зв'язного неорієнтованого графа * `A` [Топологічне сортування](src/algorithms/graph/topological-sorting) - впорядковування вершин безконтурного орієнтованого графа згідно з частковим порядком, визначеним ребрами цього графу на множині його вершин * `A` [Алгоритм Тар'яна](src/algorithms/graph/articulation-points) - алгоритм пошуку компонент сильної зв'язності в орієнтованому графі, що працює за лінійний час * `A` [Міст (теорія графів)](src/algorithms/graph/bridges) * `A` [Ейлерів ланцюг](src/algorithms/graph/eulerian-path) - ланцюг у графі, який проходить кожне ребро рівно один раз * `A` [Гамільтонів граф](src/algorithms/graph/hamiltonian-cycle) - шлях, що містить кожну вершину графа рівно один раз * `A` [Компонента сильної зв'язності графа](src/algorithms/graph/strongly-connected-components) - Алгоритм Косараджу - алгоритм для знаходження компонент сильної зв’язності орієнтованого графу * `A` [Задача комівояжера](src/algorithms/graph/travelling-salesman) - знаходження найвигіднішого маршруту, що проходить через вказані міста хоча б по одному разу * **Криптографія** * `B` [Хеш-функція](src/algorithms/cryptography/polynomial-hash) - функція, що перетворює вхідні дані будь-якого (як правило великого) розміру в дані фіксованого розміру. * `B` [Шифр Цезаря (шифр зсуву)](src/algorithms/cryptography/caesar-cipher) - симетричний моноалфавітний алгоритм шифрування, в якому кожна буква відкритого тексту заміняється на ту, що віддалена від неї в алфавіті на сталу кількість позицій * `B` [Шифр Гілла](src/algorithms/cryptography/hill-cipher) - поліграмний шифр підстановки, заснований на лінійній алгебрі * **Машинне навчання** * `B` [Нано-нейрон](https://github.com/trekhleb/nano-neuron) - 7 простих функцій JS, які ілюструють, як машини насправді можуть навчатися (пряме та зворотнє поширення) * `B` [Метод k-найближчих сусідів](src/algorithms/ml/knn) - простий непараметричний класифікаційний метод, де для класифікації об'єктів у рамках простору властивостей використовуються відстані (зазвичай евклідові), пораховані до усіх інших об'єктів * `B` [Кластеризація методом к–середніх](src/algorithms/ml/knn) - популярний метод кластеризації, — впорядкування множини об'єктів в порівняно однорідні групи. * **Без категорії** * `B` [Ханойська вежа](src/algorithms/uncategorized/hanoi-tower) * `B` [Поворот квадратної матриці](src/algorithms/uncategorized/square-matrix-rotation) * `B` [Гра стрибків](src/algorithms/uncategorized/jump-game) - зворотне відстеження, динамічне програмування (зверху вниз + знизу вгору) та жадібні приклади * `B` [Проблема унікальних шляхів](src/algorithms/uncategorized/unique-paths) - зворотне відстеження, динамічне програмування та приклади на основі Трикутника Паскаля * `B` [Дощові тераси](src/algorithms/uncategorized/rain-terraces) - проблема захоплення дощової води (динамічне програмування та версії грубої сили) * `B` [Завдання про рекурсивні сходи](src/algorithms/uncategorized/recursive-staircase) - підрахунок кількості способів досягти вершини (4 рішення) * `A` [Задача про вісім ферзів](src/algorithms/uncategorized/n-queens) * `A` [Задача про хід коня](src/algorithms/uncategorized/knight-tour) ### Парадигма програмування Парадиигма програмува́ння — це система ідей і понять, які визначають стиль написання комп'ютерних програм, а також спосіб мислення програміста. Це спосіб концептуалізації, що визначає організацію обчислень і структурування роботи, яку виконує комп'ютер. * **Метод «грубої сили» або повний перебір** - метод рішення криптографічної задачі шляхом перебору всіх можливих варіантів ключа * `B` [Лінійний пошук](src/algorithms/search/linear-search) * `B` [Дощові тераси](src/algorithms/uncategorized/rain-terraces) - задача про дощові тераси * `B` [Завдання про рекурсивні сходи](src/algorithms/uncategorized/recursive-staircase) - підрахунок кількості способів досягти вершини * `A` [Максимальний підмасив](src/algorithms/sets/maximum-subarray) * `A` [Задача комівояжера](src/algorithms/graph/travelling-salesman) - знаходження найвигіднішого маршруту, що проходить через вказані міста хоча б по одному разу * `A` [Дискретне перетворення Фур'є](src/algorithms/math/fourier-transform) - розкладання тимчасової функції (сигналу) на частотні складові * **"Жадібні" алгоритми** - простий і прямолінійний евристичний алгоритм, який приймає найкраще рішення, виходячи з наявних на кожному етапі даних, не зважаючи на можливі наслідки, сподіваючись урешті-решт отримати оптимальний розв'язок * `B` [Гра стрибків](src/algorithms/uncategorized/jump-game) - зворотне відстеження, динамічне програмування (зверху вниз + знизу вгору) та жадібні приклади * `A` [Задача пакування рюкзака](src/algorithms/sets/knapsack-problem) - приклади "0/1" та "Необмежений" * `A` [Алгоритм Дейкстри](src/algorithms/graph/dijkstra) - знаходження найкоротшого шляху від однієї вершини графа до всіх інших вершин * `A` [Алгоритм Прима](src/algorithms/graph/prim) - жадібний алгоритм побудови мінімального кістякового дерева зваженого зв'язного неорієнтованого графа * `A` [Алгоритм Крускала](src/algorithms/graph/kruskal) - алгоритм побудови мінімального кістякового дерева зваженого неорієнтовного графа * **Розділяй і володарюй** - важлива парадигма розробки алгоритмів, що полягає в рекурсивному розбитті розв'язуваної задачі на дві або більше підзадачі того ж типу, але меншого розміру, і комбінуванні їх розв'язків для отримання відповіді до вихідного завдання. Розбиття виконуються доти, поки всі підзавдання не стануть елементарними. * `B` [Двійковий пошук](src/algorithms/search/binary-search) - знаходження заданого значення у впорядкованому масиві * `B` [Ханойська вежа](src/algorithms/uncategorized/hanoi-tower) * `B` [Трикутник Паскаля](src/algorithms/math/pascal-triangle) * `B` [Алгоритм Евкліда](src/algorithms/math/euclidean-algorithm) - метод обчислення найбільшого спільного дільника (НСД) * `B` [Сортування злиттям](src/algorithms/sorting/merge-sort) * `B` [Швидке сортування](src/algorithms/sorting/quick-sort) * `B` [Пошук у глибину](src/algorithms/tree/depth-first-search) * `B` [Пошук у ширину](src/algorithms/tree/breadth-first-search) * `B` [Гра стрибків](src/algorithms/uncategorized/jump-game) - зворотне відстеження, динамічне програмування (зверху вниз + знизу вгору) та жадібні приклади * `B` [Швидке піднесення до степеня](src/algorithms/math/fast-powering) * `A` [Перестановка](src/algorithms/sets/permutations) (з повтореннями та без) * `A` [Комбінації](src/algorithms/sets/combinations) (з повтореннями та без) * **Динамічне програмування** - розділ математики, який присвячено теорії і методам розв'язання багатокрокових задач оптимального управління * `B` [Послідовність Фібоначчі](src/algorithms/math/fibonacci) - класична та закриті версії * `B` [Гра стрибків](src/algorithms/uncategorized/jump-game) - зворотне відстеження, динамічне програмування (зверху вниз + знизу вгору) та жадібні приклади * `B` [Проблема унікальних шляхів](src/algorithms/uncategorized/unique-paths) - зворотне відстеження, динамічне програмування та приклади на основі Трикутника Паскаля * `B` [Дощові тераси](src/algorithms/uncategorized/rain-terraces) - проблема захоплення дощової води (динамічне програмування та версії грубої сили) * `B` [Завдання про рекурсивні сходи](src/algorithms/uncategorized/recursive-staircase) - підрахунок кількості способів досягти вершини (4 рішення) * `A` [Відстань Левенштейна](src/algorithms/string/levenshtein-distance) - міра відмінності двох послідовностей символів (рядків) * `A` [Пошук найдовшої спільної підпослідовності](src/algorithms/sets/longest-common-subsequence) * `A` [Найбільший загальний підрядок](src/algorithms/string/longest-common-substring) * `A` [Завдання пошуку найбільшою збільшується підпослідовності](src/algorithms/sets/longest-increasing-subsequence) * `A` [Найменша загальна супер-послідовність](src/algorithms/sets/shortest-common-supersequence) * `A` [Задача пакування рюкзака](src/algorithms/sets/knapsack-problem) - приклади "0/1" та "Необмежений" * `A` [Розбиття числа](src/algorithms/math/integer-partition) * `A` [Максимальний підмасив](src/algorithms/sets/maximum-subarray) * `A` [Алгоритм Беллмана — Форда](src/algorithms/graph/bellman-ford) - алгоритм пошуку найкоротшого шляху в зваженому графі * `A` [Алгоритм Флойда — Воршелла](src/algorithms/graph/floyd-warshall) - знаходження найкоротшого шляху в зваженому графі з додатними або від'ємними вагами ребер (але без від'ємнозначних циклів) * `A` [Підбирання регулярного виразу](src/algorithms/string/regular-expression-matching) * **Пошук із зворотом** - подібно до грубої сили, намагайтеся генерувати всі можливі рішення, але кожного разу, коли ви створюєте наступне рішення, тестуєте чи він задовольняє всім умовам, і лише потім продовжуєте генерувати наступні рішення. В іншому випадку поверніться назад і рухайтесь далі іншим шляхом пошуку рішення. * `B` [Гра стрибків](src/algorithms/uncategorized/jump-game) - зворотне відстеження, динамічне програмування (зверху вниз + знизу вгору) та жадібні приклади * `B` [Проблема унікальних шляхів](src/algorithms/uncategorized/unique-paths) - зворотне відстеження, динамічне програмування та приклади на основі Трикутника Паскаля * `B` [Булеан](src/algorithms/sets/power-set) - множина всіх підмножин даної множини (бітові та зворотні рішення) * `A` [Гамільтонів граф](src/algorithms/graph/hamiltonian-cycle) - шлях, що містить кожну вершину графа рівно один раз * `A` [Задача про вісім ферзів](src/algorithms/uncategorized/n-queens) * `A` [Задача про хід коня](src/algorithms/uncategorized/knight-tour) * `A` [Комбінована сума](src/algorithms/sets/combination-sum) - знайти всі комбінації, що утворюють конкретну суму * **Метод гілок і меж** - один з поширених методів дискретної оптимізації. Метод працює на дереві рішень та визначає принципи роботи конкретних алгоритмів пошуку розв'язків, тобто, є мета-алгоритмом. Для різних задач комбінаторної оптимізації створюють спеціалізовані алгоритми гілок та меж. ## Як користуватися цим репозиторієм **Встановіть усі залежності** ``` npm install ``` **Запустіть ESLint** Запустіть для перевірки якості коду ``` npm run lint ``` **Запустіть усі тести** ``` npm test ``` **Запустіть тести за назвою** ``` npm test -- 'LinkedList' ``` **Ігрище** Ви можете побавитись зі структурами даних та алгоритмами в файлі `./src/playground/playground.js` та писати тести до них в даному файлі `./src/playground/__test__/playground.test.js`. Для перевірки, чи працює ваш код належним чином запустіть команду: ``` npm test -- 'playground' ``` ## Корисна інформація ### Список літератури [▶ Структури даних та алгоритми на YouTube](https://www.youtube.com/playlist?list=PLLXdhg_r2hKA7DPDsunoDZ-Z769jWn4R8) ### Асимптотична нотація великого О (нотація Ландау) *Асимптотична нотація великого О (нотація Ландау)* розповсюджена математична нотація для формального запису асимптотичної поведінки функцій. Широко вживається в теорії складності обчислень, інформатиці та математиці.  Джерело: [Асимптотична нотація великого О](http://bigocheatsheet.com/). Нижче наведено список деяких найбільш часто використовуваних позначень нотації Ландаута їх порівняння продуктивності з різними розмірами вхідних даних. | Нотація Ландау | Обчислення для 10 елементів | Обчислення для 100 елементів | Обчислення для 1000 елементів | | -------------- | ---------------------------- | ----------------------------- | ------------------------------- | | **O(1)** | 1 | 1 | 1 | | **O(log N)** | 3 | 6 | 9 | | **O(N)** | 10 | 100 | 1000 | | **O(N log N)** | 30 | 600 | 9000 | | **O(N^2)** | 100 | 10000 | 1000000 | | **O(2^N)** | 1024 | 1.26e+29 | 1.07e+301 | | **O(N!)** | 3628800 | 9.3e+157 | 4.02e+2567 | ### Складність операцій в структурі даних | Структура даних | Доступ | Пошук | Вставка | Видалення | Коментарі | | ----------------------- | :-------: | :-------: | :-------: | :-------: | :-------- | | **Масив** | 1 | n | n | n | | | **Купа** | n | n | 1 | 1 | | | **Черга** | n | n | 1 | 1 | | | **Зв’язаний список** | n | n | 1 | n | | | **Хеш-таблиця** | - | n | n | n | У разі ідеальної хеш-функції - O(1) | | **Бінарне дерево пошуку** | n | n | n | n | У разі збалансованого дерева витрати становитимуть O (log (n)) | | **Б-дерево** | log(n) | log(n) | log(n) | log(n) | | | **Червоно-чорне дерево** | log(n) | log(n) | log(n) | log(n) | | | **АВЛ-дерево** | log(n) | log(n) | log(n) | log(n) | | | **Фільтр Блума** | - | 1 | 1 | - | Під час пошуку можливі помилкові спрацьовування | ### Складність алгоритмів сортування масивів | Назва | Найкращий | Середній | Найгірший | Пам'ять | Стабільність | Коментарі | | --------------------- | :-------------: | :-----------------: | :-----------------: | :-------: | :-------: | :-------- | | **Сортування бульбашкою** | n | n<sup>2</sup> | n<sup>2</sup> | 1 | Так | | | **Сортування включенням** | n | n<sup>2</sup> | n<sup>2</sup> | 1 | Так | | | **Сортування вибором** | n<sup>2</sup> | n<sup>2</sup> | n<sup>2</sup> | 1 | Ні | | | **Пірамідальне сортування** | n log(n) | n log(n) | n log(n) | 1 | Ні | | | **Сортування злиттям** | n log(n) | n log(n) | n log(n) | n | Так | | | **Швидке сортування** | n log(n) | n log(n) | n<sup>2</sup> | log(n) | Ні | Швидке сортування зазвичай виконується на місці з використанням O (log (n)) додаткової пам'яті | | **Сортування Шелла** | n log(n) | залежить від послідовності проміжків | n (log(n))<sup>2</sup> | 1 | Ні | | | **Сортування підрахунком** | n + r | n + r | n + r | n + r | Так | Де r - найбільше число в масиві | | **Сортування за розрядами** | n * k | n * k | n * k | n + k | Так | Де k - довжина найдовшого ключа | ## Патронати проекту > Ви можете підтримати цей проект через ❤️️ [GitHub](https://github.com/sponsors/trekhleb) або ❤️️ [Patreon](https://www.patreon.com/trekhleb). [Люди, які підтримують цей проект](https://github.com/trekhleb/javascript-algorithms/blob/master/BACKERS.md) `∑ = 1` > ℹ️ A few more [projects](https://trekhleb.dev/projects/) and [articles](https://trekhleb.dev/blog/) about JavaScript and algorithms on [trekhleb.dev](https://trekhleb.dev)