Трассировка и метаданные

Каждый шаг алгоритма

trace запускает любую функцию сортировки и записывает каждое сравнение и каждое изменение массива — не меняя сам алгоритм. Это основа для визуализации и удобный инструмент для лабораторных: посчитать сравнения, проверить трассировку, сделанную вручную, сравнить алгоритмы на одних и тех же данных.

import { bubbleSort, trace } from 'ts-ds';

const { input, output, steps, stats } = trace(bubbleSort, [3, 1, 2]);

output; // [1, 2, 3] — исходный массив не изменяется
stats; // { comparisons: 3, reads: 10, writes: 4, swaps: 2 }
steps;
// [
//   { type: 'compare', values: [3, 1], indices: [0, 1], result: 1 },
//   { type: 'swap', i: 0, j: 1 },
//   { type: 'compare', values: [3, 2], indices: [1, 2], result: 1 },
//   { type: 'swap', i: 1, j: 2 },
//   { type: 'compare', values: [1, 2], indices: [0, 1], result: -1 },
// ]

Шаги бывают трёх видов:

Шаг	Значение
compare	Компаратор вызван со значениями values; indices — их позиции в массиве.
swap	Элементы на позициях i и j поменялись местами.
write	В позицию index записано value (сдвиг при вставках, шаг слияния, …); previous — что там было.

Воспроизведение

replay(input, steps, count) возвращает массив после первых count шагов — каждый кадр анимации:

import { replay } from 'ts-ds';

replay(input, steps, 0); // [3, 1, 2]
replay(input, steps, 2); // [1, 3, 2] — после первого обмена
replay(input, steps); // [1, 2, 3]

Сравнение алгоритмов

sortingAlgorithms описывает каждый алгоритм: название, сложность, устойчивость, сортирует ли он на месте. Вместе с trace это даёт сравнительную таблицу в несколько строк:

import { sortingAlgorithms, trace } from 'ts-ds';

const data = [5, 2, 4, 6, 1, 3];
for (const algorithm of sortingAlgorithms) {
  if (algorithm.kind === 'comparison') {
    const { stats } = trace(algorithm.sort, data);
    console.log(algorithm.name, algorithm.complexity.average, stats.comparisons, stats.swaps);
  }
}

Алгоритм	В среднем	Сравнений	Обменов	Записей
Пузырьком	O(n²)	15	9	18
Выбором	O(n²)	15	3	6
Вставками	O(n²)	12	0	14
Шелла	O(n^1.25)	11	0	12
Слиянием	O(n log n)	16	0	16
Быстрая	O(n log n)	21	9	22
Пирамидальная	O(n log n)	16	11	22

На шести элементах «быстрые» алгоритмы ещё не быстрее — разница проявляется на больших массивах. Попробуйте n = 1000.

Как это работает

Массив оборачивается в Proxy, который видит каждое чтение и запись, а компаратор — в функцию, которая считает вызовы. Алгоритмы — ровно те же функции, что вы импортируете, поэтому трассировка показывает то, что происходит на самом деле, а без trace они работают без всяких накладных расходов.

Ограничения:

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

Справочник API: trace · replay · sortingAlgorithms