Структуры данных и алгоритмы

Заметка о том, как хранить данные и как быстро с ними работать: что такое сложность алгоритма и нотация O, основные структуры данных — массив, связный список, стек, очередь, хеш-таблица, дерево, куча и граф, — а также поиск, сортировки и обход графа. Примеры — на TypeScript.

Сложность алгоритмов
Структуры данных
Алгоритмы поиска
- Линейный поиск
- Бинарный поиск
Алгоритмы сортировки
Обход графа
- Обход в ширину
- Обход в глубину
Как выбрать структуру данных

Сложность алгоритмов

Алгоритм можно написать по-разному, и на маленьких данных все версии работают мгновенно. Разница видна, когда данных становится много.

Временная сложность (англ. time complexity), или трудоёмкость, показывает, как растёт число операций с ростом размера входных данных n. Пространственная сложность (англ. space complexity) — как растёт дополнительная память.

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

Нотация O

Нотация «O большое» (англ. Big O notation) описывает верхнюю границу роста: f(n) = O(g(n)), если есть константа c > 0 и число n₀, такие что при всех n ≥ n₀ выполняется f(n) ≤ c · g(n). Проще: O показывает, во сколько раз вырастет работа, когда данных станет больше, — без констант и младших слагаемых.

Как посчитать:

выразить число шагов через n: один проход по массиву — n шагов, вложенный цикл по тому же массиву — n · n;
отбросить константы: O(2n) = O(n);
оставить самое быстрорастущее слагаемое: O(n² + n) = O(n²);
последовательные части складываются, вложенные — перемножаются.

Обозначение	Название	Пример	Шагов при n = 1000
`O(1)`	константная	доступ к элементу массива по индексу	1
`O(log n)`	логарифмическая	бинарный поиск	≈ 10
`O(n)`	линейная	линейный поиск	1000
`O(n log n)`	линейно-логарифмическая	сортировка слиянием	≈ 10 000
`O(n²)`	квадратичная	сортировка пузырьком	1 000 000
`O(2ⁿ)`	экспоненциальная	перебор всех подмножеств	≈ 10³⁰¹

Если увеличить данные до миллиона, разница станет огромной:

for (const n of [10, 1000, 1_000_000]) {
  console.log(n, Math.round(Math.log2(n)), n, Math.round(n * Math.log2(n)), n * n);
}
/* n        log n  n        n log n     n²
10       3      10       33          100
1000     10     1000     9966        1000000
1000000  20     1000000  19931569    1000000000000 */

Логарифмический алгоритм на миллионе элементов делает около 20 шагов, а квадратичный — триллион.

Лучший, средний и худший случай

Число шагов зависит не только от n, но и от самих данных. Линейный поиск найдёт первый элемент за один шаг (лучший случай), а последний — за n шагов (худший). Быстрая сортировка в среднем работает за O(n log n), но на неудачных данных — за O(n²) (пример).

Когда говорят просто «сложность», обычно имеют в виду худший случай: он даёт гарантию.

Амортизированная сложность

Амортизированная сложность (англ. amortized complexity) — средняя стоимость операции на длинной последовательности операций. Классический пример — динамический массив (англ. dynamic array): когда место заканчивается, он выделяет вдвое больше и копирует все элементы. Одна такая вставка стоит O(n), но случается редко:

class DynamicArray {
  private data = new Array<number>(1);
  private length = 0;
  copies = 0;

  push(value: number): void {
    if (this.length === this.data.length) {
      /* место кончилось: выделяем вдвое больше и копируем всё */
      const bigger = new Array<number>(this.data.length * 2);
      for (let i = 0; i < this.length; i++) {
        bigger[i] = this.data[i];
        this.copies++;
      }
      this.data = bigger;
    }
    this.data[this.length++] = value;
  }
}

const dynamicArray = new DynamicArray();
for (let i = 0; i < 1_000_000; i++) dynamicArray.push(i);
console.log(dynamicArray.copies); // 1048575

На миллион вставок пришлось около миллиона копирований — примерно одно на вставку. Значит, вставка в конец стоит O(1) амортизированно. Так же описан ArrayList в Java: добавление — за амортизированное константное время, то есть n добавлений стоят O(n) (документация). Массивы в JavaScript тоже растут сами, а как именно — решает движок.

Структуры данных

Что такое структура данных

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

Важно различать «что» и «как». Абстрактный тип данных (англ. abstract data type, ADT) описывает, какие операции доступны: например, у стека — положить и снять верхний элемент. Структура данных — как это устроено внутри: тот же стек можно построить на массиве или на связном списке. Операции одни и те же, а их стоимость может отличаться.

Типы значений — числа, строки, логические — разобраны в заметке про типы данных.

Массив

Массив (англ. array) — элементы, доступные по номеру (индексу). Классический массив (например, в C) хранит элементы подряд в памяти: адрес элемента = начало массива + индекс × размер элемента. Поэтому доступ по индексу стоит O(1), а вставка и удаление в середине — O(n): все элементы после нужно сдвинуть.

const numbers = [10, 20, 30, 40];
console.log(numbers[2]); // 30

/* вставка в середину: 20, 30 и 40 сдвигаются вправо */
numbers.splice(1, 0, 15);
console.log(numbers); // [ 10, 15, 20, 30, 40 ]

В JavaScript Array — это объект, который по-особому обрабатывает ключи-индексы (ECMA-262); как он хранится в памяти — дело движка. Но стоимость операций похожа: push и pop работают с концом массива и дёшевы, а shift и unshift — с началом. По спецификации shift переносит каждый оставшийся элемент на одну позицию влево (ECMA-262), то есть стоит O(n). Замер в Node 24: опустошить массив через shift:

Элементов	Время
50 000	≈ 0,15 с
100 000	≈ 0,6 с
200 000	≈ 2,4 с

Элементов вдвое больше — времени вчетверо: каждый shift стоит O(n), а все вместе — O(n²). Проход по тем же массивам по индексу занял единицы миллисекунд.

Связный список

Связный список (англ. linked list) состоит из узлов: каждый хранит значение и ссылку на следующий узел. В двусвязном списке (англ. doubly linked list) есть ссылка и на предыдущий.

Вставка и удаление в начале стоят O(1): достаточно поменять ссылки, ничего не сдвигая. Зато доступ по индексу — O(n): до нужного узла приходится идти от начала. LinkedList в Java — двусвязный список, и операции по индексу проходят его с начала или с конца — откуда ближе (документация).

type ListNode<T> = { value: T; next: ListNode<T> | null };

class LinkedList<T> {
  private head: ListNode<T> | null = null;

  /* вставка в начало: O(1) */
  prepend(value: T): void {
    this.head = { value, next: this.head };
  }

  /* доступ по индексу: O(n), идём от начала */
  at(index: number): T | undefined {
    let node = this.head;
    for (let i = 0; node && i < index; i++) node = node.next;
    return node?.value;
  }

  toArray(): T[] {
    const result: T[] = [];
    for (let node = this.head; node; node = node.next) result.push(node.value);
    return result;
  }
}

const list = new LinkedList<string>();
list.prepend('c');
list.prepend('b');
list.prepend('a');
console.log(list.toArray()); // [ 'a', 'b', 'c' ]
console.log(list.at(2)); // c

Стек

Стек (англ. stack) работает по принципу LIFO (англ. Last In, First Out): последним пришёл — первым ушёл. Операции: положить наверх (англ. push) и снять сверху (англ. pop), обе — O(1).

Жизненный пример: стопка тарелок — берут верхнюю, ту, которую положили последней. В программах стек — это кнопка «Отменить» (отменяется последнее действие) и стек вызовов: функция, вызванная последней, завершается первой. Слишком глубокая рекурсия переполняет его.

Классическая задача — проверить скобки: открывающую кладём в стек, а закрывающая должна совпасть с верхней.

const isBalanced = (text: string): boolean => {
  const pairs: Record<string, string> = { ')': '(', ']': '[', '}': '{' };
  const stack: string[] = [];
  for (const char of text) {
    if ('([{'.includes(char)) stack.push(char);
    else if (char in pairs && stack.pop() !== pairs[char]) return false;
  }
  return stack.length === 0;
};

console.log(isBalanced('{[()()]}')); // true
console.log(isBalanced('([)]')); // false
console.log(isBalanced('((')); // false

Очередь

Очередь (англ. queue) работает по принципу FIFO (англ. First In, First Out): первым пришёл — первым ушёл. Операции: добавить в конец (англ. enqueue) и взять из начала (англ. dequeue), обе — O(1).

Жизненный пример: очередь в кассу. В программах — задачи, которые обрабатывают по порядку: печать документов, сообщения в брокере, вершины при обходе графа в ширину.

Массив с push и shift подходит только для маленьких очередей: как мы видели, shift стоит O(n). Быстрая очередь запоминает, где её начало, и не сдвигает элементы при каждом извлечении:

class Queue<T> {
  private items: T[] = [];
  private head = 0;

  enqueue(item: T): void {
    this.items.push(item);
  }

  dequeue(): T | undefined {
    if (this.head === this.items.length) return undefined;
    const item = this.items[this.head++];
    /* когда прочитанных элементов больше половины — выбрасываем их одним махом */
    if (this.head * 2 > this.items.length) {
      this.items = this.items.slice(this.head);
      this.head = 0;
    }
    return item;
  }

  get size(): number {
    return this.items.length - this.head;
  }
}

const queue = new Queue<string>();
queue.enqueue('Анна');
queue.enqueue('Борис');
queue.enqueue('Вера');
console.log(queue.dequeue(), queue.size); // Анна 2

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

Разновидности: дек (англ. deque, double-ended queue) позволяет добавлять и забирать с обоих концов, а очередь с приоритетом (англ. priority queue) отдаёт не самый старый, а самый важный элемент — её строят на куче.

Хеш-таблица

Хеш-функция (англ. hash function) превращает ключ в число — хеш (англ. hash). У одинаковых ключей хеш всегда одинаковый.

Хеш-таблица (англ. hash table) — массив корзин (англ. buckets). Номер корзины — остаток от деления хеша на число корзин, поэтому искать ключ нужно только в одной корзине. Поиск, вставка и удаление в среднем стоят O(1).

Коллизия (англ. collision) — два разных ключа попали в одну корзину. Её решают двумя способами:

метод цепочек (англ. separate chaining): в корзине лежит список пар «ключ — значение»;
открытая адресация (англ. open addressing): если ячейка занята, ищут следующую свободную.

Если все ключи попадут в одну корзину, поиск выродится в перебор за O(n) — это худший случай. Чтобы корзины не переполнялись, следят за коэффициентом заполнения (англ. load factor) — числом элементов на корзину. Когда он становится большим, корзин делают вдвое больше и раскладывают ключи заново (англ. rehashing). Например, HashMap в Java обещает константное время get и put, если хеш-функция хорошо раскладывает ключи по корзинам; коэффициент заполнения по умолчанию — 0,75, а при превышении корзин становится примерно вдвое больше (документация). Пример ниже использует те же 0,75.

class HashTable<V> {
  private buckets: [string, V][][] = Array.from({ length: 4 }, () => []);
  private count = 0;

  private hash(key: string): number {
    let hash = 0;
    for (const char of key) hash = (hash * 31 + char.charCodeAt(0)) >>> 0;
    return hash;
  }

  private bucketOf(key: string): [string, V][] {
    return this.buckets[this.hash(key) % this.buckets.length];
  }

  set(key: string, value: V): void {
    const bucket = this.bucketOf(key);
    const entry = bucket.find(([k]) => k === key);
    if (entry) {
      entry[1] = value;
      return;
    }
    bucket.push([key, value]); /* коллизия? просто ещё одна пара в той же корзине */
    this.count++;
    if (this.count / this.buckets.length > 0.75) this.resize();
  }

  get(key: string): V | undefined {
    return this.bucketOf(key).find(([k]) => k === key)?.[1];
  }

  private resize(): void {
    const entries = this.buckets.flat();
    this.buckets = Array.from({ length: this.buckets.length * 2 }, () => []);
    this.count = 0;
    for (const [key, value] of entries) this.set(key, value);
  }

  get capacity(): number {
    return this.buckets.length;
  }
}

const prices = new HashTable<number>();
prices.set('margherita', 10);
prices.set('pepperoni', 12);
prices.set('hawaii', 11);
prices.set('diavola', 13);
console.log(prices.get('pepperoni'), prices.get('calzone'), prices.capacity); // 12 undefined 8

В JavaScript для этого есть Map и Set. Спецификация требует реализовать их хеш-таблицами или другим способом, который в среднем даёт доступ быстрее, чем за линейное время (ECMA-262). Ключом Map может быть любое значение, даже объект, а обходит Map ключи в порядке добавления. У обычного объекта порядок другой: сначала ключи-индексы по возрастанию, потом строковые в порядке создания (ECMA-262):

const scores = { b: 1, 10: 'x', a: 2, 2: 'y' };
console.log(Object.keys(scores)); // [ '2', '10', 'b', 'a' ]

const scoresMap = new Map<string | number, string | number>([['b', 1], [10, 'x'], ['a', 2], [2, 'y']]);
console.log([...scoresMap.keys()]); // [ 'b', 10, 'a', 2 ]

/* Set хранит только уникальные значения */
console.log(new Set([3, 1, 3, 2, 1]).size); // 3

Итог: найти элемент в неотсортированном массиве стоит O(n), а в хеш-таблице — O(1) в среднем.

Дерево

Дерево (англ. tree) — узлы, связанные без циклов: у каждого узла, кроме корня (англ. root), ровно один родитель. Узлы без детей называют листьями (англ. leaves), а число уровней — высотой (англ. height). Примеры — дерево папок на диске и DOM страницы.

Двоичное дерево поиска (англ. binary search tree, BST) — дерево, где у узла не больше двух детей, и всё, что левее, меньше узла, а всё, что правее, — больше. Поиск и вставка идут от корня вниз и стоят O(h), где h — высота. Всё решает форма дерева: если вставлять ключи по возрастанию, дерево вытягивается в цепочку.

class TreeNode {
  left: TreeNode | null = null;
  right: TreeNode | null = null;
  constructor(public value: number) {}
}

const insert = (root: TreeNode | null, value: number): TreeNode => {
  const node = new TreeNode(value);
  if (!root) return node;
  let current = root;
  while (true) {
    if (value < current.value) {
      if (!current.left) { current.left = node; break; }
      current = current.left;
    } else {
      if (!current.right) { current.right = node; break; }
      current = current.right;
    }
  }
  return root;
};

const height = (root: TreeNode | null): number => {
  let levels = 0;
  for (let level = root ? [root] : []; level.length > 0; levels++) {
    level = level.flatMap((node) => [node.left, node.right]).filter((child): child is TreeNode => child !== null);
  }
  return levels;
};

/* 1000 ключей по возрастанию и те же ключи вперемешку */
const ascending = Array.from({ length: 1000 }, (_, i) => i + 1);
let seed = 42;
const random = () => (seed = (seed * 1_103_515_245 + 12_345) % 2 ** 31) / 2 ** 31;
const shuffled = [...ascending];
for (let i = shuffled.length - 1; i > 0; i--) {
  const j = Math.floor(random() * (i + 1));
  [shuffled[i], shuffled[j]] = [shuffled[j], shuffled[i]];
}

let chain: TreeNode | null = null;
for (const key of ascending) chain = insert(chain, key);
let bushy: TreeNode | null = null;
for (const key of shuffled) bushy = insert(bushy, key);

console.log(height(chain), height(bushy)); // 1000 24

В цепочке поиск стоит столько же, сколько в списке, — O(n). Самобалансирующиеся деревья — например, АВЛ-деревья и красно-чёрные, — после вставок перестраиваются и держат высоту O(log n), поэтому поиск, вставка и удаление в них — O(log n). Например, TreeMap в Java построен на красно-чёрном дереве и гарантирует log(n) для get, put и remove (документация).

В базах данных деревья хранят индексы. В PostgreSQL CREATE INDEX по умолчанию создаёт B-дерево (англ. B-tree) — оно подходит для поиска по равенству и по диапазону (документация); подробнее об индексах — в заметке про базы данных. Ещё один способ хранить отсортированные данные — список с пропусками.

Список с пропусками

Список с пропусками (англ. skip list) — вероятностная структура данных, основанная на нескольких параллельных отсортированных связных списках. Позволяет производить поиск и вставку сложности O(log n) в среднем в упорядоченной последовательности из n элементов, что сравнимо с двоичным деревом.

Нижний уровень — обычный отсортированный связный список со всеми элементами. Каждый уровень выше содержит часть узлов и «перепрыгивает» через остальные. Поиск начинается с верхнего уровня: идём вправо, пока следующий узел не больше искомого, а потом спускаемся на уровень ниже:

уровень 2:  1 ────────────→ 9
уровень 1:  1 ────→ 5 ────→ 9
уровень 0:  1 → 3 → 5 → 7 → 9 → 11

поиск 7: 1 (ур. 2) → вниз → 5 (ур. 1) → вниз → 7 (ур. 0)

Если бы каждый второй узел указывал на узел через один, каждый четвёртый — через три и так далее, хватило бы около log₂ n шагов, но держать такой порядок при вставках слишком дорого. Поэтому уровень нового узла выбирают случайно: список балансируется вероятностно, а не строго. Автор структуры, Уильям Пью, предложил её как замену сбалансированным деревьям: вставка и удаление получаются проще (статья).

Например, Redis хранит отсортированные множества в списке с пропусками вместе с хеш-таблицей, и добавление стоит O(log N) (документация).

Куча

Двоичная куча (англ. binary heap) — двоичное дерево, где родитель не больше своих детей (так устроена минимальная куча, англ. min-heap). Поэтому наименьший элемент всегда в корне. Куча заполняется по уровням слева направо, и её удобно хранить в массиве: дети элемента i лежат на местах 2i + 1 и 2i + 2, а родитель — на месте ⌊(i − 1) / 2⌋.

Посмотреть минимум стоит O(1), а вставка и извлечение минимума — O(log n): элемент «всплывает» или «тонет» на высоту дерева. На куче строят очередь с приоритетом. Так работает PriorityQueue в Java: добавление и извлечение — O(log n), просмотр первого элемента — за константное время, а поиск произвольного — за линейное (документация):

class MinHeap<T> {
  private items: { priority: number; value: T }[] = [];

  push(priority: number, value: T): void {
    this.items.push({ priority, value });
    let i = this.items.length - 1;
    /* всплываем, пока родитель больше */
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2);
      if (this.items[parent].priority <= this.items[i].priority) break;
      [this.items[parent], this.items[i]] = [this.items[i], this.items[parent]];
      i = parent;
    }
  }

  pop(): T | undefined {
    const top = this.items[0];
    const last = this.items.pop();
    if (this.items.length > 0 && last) {
      this.items[0] = last;
      /* тонем, пока какой-то ребёнок меньше */
      let i = 0;
      while (true) {
        const left = 2 * i + 1;
        const right = left + 1;
        let smallest = i;
        if (left < this.items.length && this.items[left].priority < this.items[smallest].priority) smallest = left;
        if (right < this.items.length && this.items[right].priority < this.items[smallest].priority) smallest = right;
        if (smallest === i) break;
        [this.items[smallest], this.items[i]] = [this.items[i], this.items[smallest]];
        i = smallest;
      }
    }
    return top?.value;
  }
}

/* задачи с приоритетом: чем меньше число, тем срочнее */
const tasks = new MinHeap<string>();
tasks.push(3, 'обновить документацию');
tasks.push(1, 'починить оплату');
tasks.push(2, 'ответить клиенту');
console.log(tasks.pop(), '→', tasks.pop(), '→', tasks.pop()); // починить оплату → ответить клиенту → обновить документацию

Граф

Граф (англ. graph) — вершины (англ. vertices) и рёбра (англ. edges) между ними. Рёбра бывают направленными (подписка в соцсети) и ненаправленными (дружба), а у взвешенного графа у рёбер есть вес — например, длина дороги. Теория — в заметке про дискретную математику.

Граф хранят двумя способами:

матрица смежности (англ. adjacency matrix) — таблица V × V, где на пересечении отмечено ребро. Проверить, есть ли ребро, — O(1), но памяти нужно O(V²) даже для почти пустого графа;
список смежности (англ. adjacency list) — у каждой вершины свой список соседей. Памяти — O(V + E), поэтому для разреженных графов его используют чаще.

/* схема метро: у каждой станции — список соседних */
const metro = new Map<string, string[]>([
  ['Арбатская', ['Смоленская', 'Библиотека', 'Кропоткинская']],
  ['Смоленская', ['Арбатская', 'Киевская']],
  ['Киевская', ['Смоленская', 'Парк Культуры']],
  ['Библиотека', ['Арбатская', 'Боровицкая']],
  ['Боровицкая', ['Библиотека', 'Полянка']],
  ['Кропоткинская', ['Арбатская', 'Парк Культуры']],
  ['Парк Культуры', ['Кропоткинская', 'Киевская']],
  ['Полянка', ['Боровицкая']],
]);

console.log(metro.get('Арбатская')?.length); // 3

Схема упрощённая: это учебный граф, а не настоящая карта. Как по нему искать путь — в разделе обход графа.

Сравнение структур данных

Структура	Доступ	Поиск	Вставка	Удаление	Когда использовать
Массив	`O(1)` по индексу	`O(n)`	`O(1)` в конец амортизированно, `O(n)` в середину	`O(1)` с конца, `O(n)` из середины	данные по порядку, доступ по номеру
Связный список	`O(n)`	`O(n)`	`O(1)` в начало	`O(1)` из начала	частые вставки и удаления в начале
Стек	только верх	—	`O(1)`	`O(1)`	отмена действий, вложенность, рекурсия
Очередь	только начало	—	`O(1)`	`O(1)`	задачи по порядку, обход в ширину
Хеш-таблица	`O(1)` по ключу в среднем	`O(1)` в среднем	`O(1)` в среднем	`O(1)` в среднем	поиск по ключу, уникальность
Сбалансированное дерево поиска	—	`O(log n)`	`O(log n)`	`O(log n)`	отсортированные данные, поиск по диапазону
Куча	минимум за `O(1)`	`O(n)`	`O(log n)`	минимум за `O(log n)`	очередь с приоритетом

Алгоритмы поиска

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

Линейный поиск (англ. linear search) проверяет элементы по очереди, пока не найдёт нужный. Работает с любым массивом, даже неотсортированным, и стоит O(n). Именно так устроены indexOf, includes и find.

const linearSearch = (items: number[], target: number): number => {
  for (let i = 0; i < items.length; i++) {
    if (items[i] === target) return i;
  }
  return -1;
};

console.log(linearSearch([7, 3, 9, 1], 9)); // 2
console.log(linearSearch([7, 3, 9, 1], 5)); // -1

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

Бинарный поиск (англ. binary search) работает только с отсортированным массивом: сравниваем искомое с серединой и отбрасываем половину, где его быть не может. Каждый шаг делит область поиска пополам, поэтому шагов — O(log n).

Жизненный пример: угадать число от 1 до 100, спрашивая «больше или меньше?». Если каждый раз называть середину, хватит семи вопросов.

const binarySearch = (items: number[], target: number) => {
  let low = 0;
  let high = items.length - 1;
  let steps = 0;
  while (low <= high) {
    steps++;
    const middle = Math.floor((low + high) / 2);
    if (items[middle] === target) return { index: middle, steps };
    if (items[middle] < target) low = middle + 1;
    else high = middle - 1;
  }
  return { index: -1, steps };
};

/* миллион чётных чисел по возрастанию */
const evens = Array.from({ length: 1_000_000 }, (_, i) => i * 2);
console.log(binarySearch(evens, 1_337_000)); // { index: 668500, steps: 16 }
console.log(binarySearch(evens, 7)); // { index: -1, steps: 20 }

Даже когда числа нет, хватает двадцати шагов на миллион элементов, а линейному поиску понадобился бы миллион.

Бинарный поиск легко написать с ошибкой. В 2006 году Джошуа Блох рассказал, что строка int mid = (low + high) / 2; в Java ломается, когда сумма превышает максимальный int (2³¹ − 1): она переполняется и становится отрицательной (Google Research). В JavaScript числа — 64-битные с плавающей точкой (ECMA-262), и сумма не переполнится. Но сдвиг >> превращает число в 32-битное целое (ECMA-262), поэтому популярная запись (low + high) >> 1 ломается на тех же значениях:

/* сумма больше 2³¹ − 1, как в случае Блоха */
const low = 2 ** 30;
const high = 2 ** 31 - 1;
console.log((low + high) >> 1); // -536870913
console.log(Math.floor((low + high) / 2)); // 1610612735

Алгоритмы сортировки

Чтобы сравнивать сортировки, будем считать сравнения элементов. Для примеров — массив из 1000 чисел в трёх вариантах: по возрастанию, по убыванию и вперемешку (перемешивание повторяемое, с фиксированным начальным значением).

let comparisons = 0;
const less = (a: number, b: number): boolean => {
  comparisons++;
  return a < b;
};

const sortedInput = Array.from({ length: 1000 }, (_, i) => i);
const reversedInput = [...sortedInput].reverse();
let mixSeed = 7;
const mixRandom = () => (mixSeed = (mixSeed * 1_103_515_245 + 12_345) % 2 ** 31) / 2 ** 31;
const mixedInput = [...sortedInput];
for (let i = mixedInput.length - 1; i > 0; i--) {
  const j = Math.floor(mixRandom() * (i + 1));
  [mixedInput[i], mixedInput[j]] = [mixedInput[j], mixedInput[i]];
}

/* запускает сортировку на копии и возвращает число сравнений */
const measure = (sort: (items: number[]) => number[], input: number[]): number => {
  comparisons = 0;
  const result = sort([...input]);
  if (result.some((value, i) => i > 0 && value < result[i - 1])) throw new Error('не отсортировано');
  return comparisons;
};

Сортировка пузырьком

Сортировка пузырьком (англ. bubble sort) сравнивает соседние элементы и меняет их местами, если они стоят не по порядку. За один проход самый большой элемент «всплывает» в конец. Если за проход не было ни одного обмена, массив уже отсортирован, и можно остановиться.

const bubbleSort = (items: number[]): number[] => {
  for (let end = items.length - 1; end > 0; end--) {
    let swapped = false;
    for (let i = 0; i < end; i++) {
      if (less(items[i + 1], items[i])) {
        [items[i], items[i + 1]] = [items[i + 1], items[i]];
        swapped = true;
      }
    }
    if (!swapped) break; /* обменов не было — всё на местах */
  }
  return items;
};

console.log(measure(bubbleSort, sortedInput), measure(bubbleSort, reversedInput)); // 999 499500

На отсортированном массиве — один проход, O(n); на обратном — n(n − 1) / 2 сравнений, O(n²).

Сортировка вставками

Сортировка вставками (англ. insertion sort) берёт элементы по одному и вставляет на своё место в уже отсортированную левую часть — так раскладывают карты в руке. O(n²) в худшем случае, но на почти отсортированных данных почти O(n).

const insertionSort = (items: number[]): number[] => {
  for (let i = 1; i < items.length; i++) {
    const current = items[i];
    let j = i - 1;
    while (j >= 0 && less(current, items[j])) {
      items[j + 1] = items[j]; /* сдвигаем больший вправо */
      j--;
    }
    items[j + 1] = current;
  }
  return items;
};

console.log(measure(insertionSort, sortedInput), measure(insertionSort, reversedInput)); // 999 499500

Сортировка слиянием

Сортировка слиянием (англ. merge sort) делит массив пополам, сортирует половины рекурсивно и сливает две отсортированные половины в одну. Уровней деления — log n, на каждом сливается всего n элементов, поэтому всегда O(n log n). Цена — O(n) дополнительной памяти.

const mergeSort = (items: number[]): number[] => {
  if (items.length <= 1) return items;
  const middle = Math.floor(items.length / 2);
  const left = mergeSort(items.slice(0, middle));
  const right = mergeSort(items.slice(middle));

  const merged: number[] = [];
  let i = 0;
  let j = 0;
  while (i < left.length && j < right.length) {
    /* при равенстве берём левый — так сохраняется порядок равных */
    merged.push(less(right[j], left[i]) ? right[j++] : left[i++]);
  }
  return merged.concat(left.slice(i), right.slice(j));
};

console.log(measure(mergeSort, sortedInput), measure(mergeSort, reversedInput), measure(mergeSort, mixedInput)); // 4932 5044 8715

Быстрая сортировка

Быстрая сортировка (англ. quicksort) выбирает опорный элемент (англ. pivot), раскладывает остальные на меньшие и большие и сортирует обе части рекурсивно. В среднем — O(n log n), и в отличие от слияния она переставляет элементы на месте, без дополнительного массива. Но если опорный элемент каждый раз оказывается крайним, части получаются размером n − 1 и 0, и сложность вырождается в O(n²):

const quickSort = (choosePivot: (low: number, high: number) => number) => (items: number[]): number[] => {
  const sort = (low: number, high: number): void => {
    if (low >= high) return;
    const pivotIndex = choosePivot(low, high);
    [items[pivotIndex], items[high]] = [items[high], items[pivotIndex]];
    const pivot = items[high];
    let border = low;
    for (let i = low; i < high; i++) {
      if (less(items[i], pivot)) {
        [items[i], items[border]] = [items[border], items[i]];
        border++;
      }
    }
    [items[border], items[high]] = [items[high], items[border]];
    sort(low, border - 1);
    sort(border + 1, high);
  };
  sort(0, items.length - 1);
  return items;
};

const lastAsPivot = quickSort((_low, high) => high);
const middleAsPivot = quickSort((low, high) => Math.floor((low + high) / 2));

console.log(measure(lastAsPivot, sortedInput), measure(middleAsPivot, sortedInput)); // 499500 7987

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

Сортировка в JavaScript

Array.prototype.sort без аргумента сравнивает элементы как строки (ECMA-262), поэтому числа нужно сортировать с функцией сравнения:

console.log([10, 9, 1].sort()); // [ 1, 10, 9 ]
console.log([10, 9, 1].sort((a, b) => a - b)); // [ 1, 9, 10 ]

Спецификация требует, чтобы сортировка была устойчивой (англ. stable): элементы, равные для функции сравнения, сохраняют исходный порядок (ECMA-262). Это позволяет сортировать по нескольким признакам по очереди:

const people = [
  { name: 'Вера', city: 'Ереван' },
  { name: 'Анна', city: 'Тбилиси' },
  { name: 'Борис', city: 'Ереван' },
];
/* сначала по имени, потом по городу: внутри города имена остаются по алфавиту */
const byCity = [...people].sort((a, b) => a.name.localeCompare(b.name)).sort((a, b) => a.city.localeCompare(b.city));
console.log(byCity.map((person) => person.name).join(', ')); // Борис, Вера, Анна

sort меняет сам массив; чтобы получить отсортированную копию, есть toSorted (ECMA-262).

Движок V8 (на нём работают Chrome и Node.js) начиная с версии 7.0 сортирует алгоритмом Timsort — устойчивым вариантом сортировки слиянием, который Тим Питерс придумал для Python в 2002 году. Timsort ищет уже отсортированные участки (англ. runs), в том числе отсортированные в обратную сторону (блог V8). Уже отсортированный массив — это один такой участок, и он сортируется за O(n); худший случай — O(n log n). Эти свойства и устойчивость стали причинами выбрать Timsort, а не быструю сортировку. Проверим, сколько сравнений он делает на готовом порядке:

const countSortComparisons = (input: number[]): number => {
  let count = 0;
  [...input].sort((a, b) => {
    count++;
    return a - b;
  });
  return count;
};

const thousand = Array.from({ length: 1000 }, (_, i) => i);
console.log(countSortComparisons(thousand), countSortComparisons([...thousand].reverse())); // 999 999

Сравнение сортировок

Алгоритм	Лучший случай	Средний	Худший	Доп. память	Устойчивая
Пузырьком	`O(n)`	`O(n²)`	`O(n²)`	`O(1)`	да
Вставками	`O(n)`	`O(n²)`	`O(n²)`	`O(1)`	да
Слиянием	`O(n log n)`	`O(n log n)`	`O(n log n)`	`O(n)`	да
Быстрая	`O(n log n)`	`O(n log n)`	`O(n²)`	`O(log n)` на рекурсию в среднем	нет
Timsort (`sort` в V8)	`O(n)`	`O(n log n)`	`O(n log n)`	временные массивы для слияний	да

Сравнения на тех же 1000 элементах:

Алгоритм	По возрастанию	По убыванию	Вперемешку
Пузырьком	999	499 500	498 554
Вставками	999	499 500	254 767
Слиянием	4932	5044	8715
Быстрая, опорный — последний	499 500	499 500	10 837
Быстрая, опорный — середина	7987	8406	11 952

На перемешанных данных квадратичные сортировки делают сотни тысяч сравнений, а слияние и быстрая — около десяти тысяч. Число сравнений — не единственная цена: важны ещё перестановки и дополнительная память.

Обход графа

Обойти граф — посетить все вершины, достижимые из начальной, по одному разу. Оба способа ниже стоят O(V + E): каждая вершина и каждое ребро рассматриваются один раз.

Обход в ширину

Обход в ширину (англ. breadth-first search, BFS) идёт волнами: сначала все соседи начальной вершины, потом их соседи и так далее. Вершины ждут своей очереди в очереди. Поэтому в графе без весов BFS находит путь с наименьшим числом рёбер — например, маршрут с наименьшим числом перегонов:

const subway = new Map<string, string[]>([
  ['Арбатская', ['Смоленская', 'Библиотека', 'Кропоткинская']],
  ['Смоленская', ['Арбатская', 'Киевская']],
  ['Киевская', ['Смоленская', 'Парк Культуры']],
  ['Библиотека', ['Арбатская', 'Боровицкая']],
  ['Боровицкая', ['Библиотека', 'Полянка']],
  ['Кропоткинская', ['Арбатская', 'Парк Культуры']],
  ['Парк Культуры', ['Кропоткинская', 'Киевская']],
  ['Полянка', ['Боровицкая']],
]);

const shortestPath = (graph: Map<string, string[]>, from: string, to: string): string[] => {
  const previous = new Map<string, string | null>([[from, null]]);
  const waiting = [from];
  for (let head = 0; head < waiting.length; head++) {
    const station = waiting[head];
    if (station === to) break;
    for (const next of graph.get(station) ?? []) {
      if (!previous.has(next)) {
        previous.set(next, station); /* запоминаем, откуда пришли */
        waiting.push(next);
      }
    }
  }
  if (!previous.has(to)) return [];
  const path: string[] = [];
  for (let station: string | null = to; station !== null; station = previous.get(station) ?? null) path.unshift(station);
  return path;
};

console.log(shortestPath(subway, 'Полянка', 'Киевская').join(' → ')); // Полянка → Боровицкая → Библиотека → Арбатская → Смоленская → Киевская

Обход в глубину

Обход в глубину (англ. depth-first search, DFS) идёт по одной ветке до конца и только потом возвращается назад. Его пишут рекурсией или со стеком. Обход в глубину используют, чтобы найти все достижимые вершины, проверить, есть ли в графе цикл, или упорядочить задачи по зависимостям:

/* зависимости сборки: чтобы собрать приложение, сначала нужны его зависимости */
const dependencies = new Map<string, string[]>([
  ['app', ['ui', 'api']],
  ['ui', ['utils']],
  ['api', ['utils', 'db']],
  ['utils', []],
  ['db', []],
]);

const buildOrder = (graph: Map<string, string[]>, start: string): string[] => {
  const visited = new Set<string>();
  const order: string[] = [];
  const visit = (node: string): void => {
    if (visited.has(node)) return;
    visited.add(node);
    for (const dependency of graph.get(node) ?? []) visit(dependency);
    order.push(node); /* узел — после всех своих зависимостей */
  };
  visit(start);
  return order;
};

console.log(buildOrder(dependencies, 'app').join(' → ')); // utils → ui → db → api → app

Такой порядок называют топологической сортировкой (англ. topological sort): каждый узел идёт после всего, от чего он зависит.

Как выбрать структуру данных

Задача	Структура	Почему
отменить последнее действие	стек	последним пришёл — первым ушёл
обработать заказы по порядку	очередь	первым пришёл — первым ушёл
найти пользователя по email	хеш-таблица (`Map`)	поиск по ключу за `O(1)` в среднем
убрать дубликаты	`Set`	хранит только уникальные значения
искать по диапазону в отсортированных данных	сбалансированное дерево, B-дерево или список с пропусками	поиск, вставка и удаление за `O(log n)`
выбирать самую срочную задачу	куча	минимум — за `O(1)`, вставка и извлечение — за `O(log n)`
построить маршрут или порядок сборки	граф	обход в ширину или в глубину
часто читать по номеру	массив	доступ по индексу за `O(1)`

Navigation Menu

Repository navigation

DataStructures.md

DataStructures.md

Структуры данных и алгоритмы

Сложность алгоритмов

Нотация O

Лучший, средний и худший случай

Амортизированная сложность

Структуры данных

Что такое структура данных

Массив

Связный список

Стек

Очередь

Хеш-таблица

Дерево

Список с пропусками

Куча

Граф

Сравнение структур данных

Алгоритмы поиска

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

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

Алгоритмы сортировки

Сортировка пузырьком

Сортировка вставками

Сортировка слиянием

Быстрая сортировка

Сортировка в JavaScript

Сравнение сортировок

Обход графа

Обход в ширину

Обход в глубину

Как выбрать структуру данных

FilesExpand file tree

DataStructures.md

Latest commit

History

DataStructures.md

File metadata and controls

Структуры данных и алгоритмы

Сложность алгоритмов

Нотация O

Лучший, средний и худший случай

Амортизированная сложность

Структуры данных

Что такое структура данных

Массив

Связный список

Стек

Очередь

Хеш-таблица

Дерево

Список с пропусками

Куча

Граф

Сравнение структур данных

Алгоритмы поиска

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

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

Алгоритмы сортировки

Сортировка пузырьком

Сортировка вставками

Сортировка слиянием

Быстрая сортировка

Сортировка в JavaScript

Сравнение сортировок

Обход графа

Обход в ширину

Обход в глубину

Как выбрать структуру данных