Визуализация алгоритмов

Специалист по дата-майнингу и визуализации данных Майк Босток (Mike Bostock) опубликовал великолепную подборку с визуализацией различных алгоритмов.

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

Проще говоря, зрение помогает нам думать.

Майк Босток уверен, что его работа помогает лучше понять работу алгоритмов. Более того, если кто-то хочет сам разобраться в работе того или иного алгоритма, то лучше всего попробовать сделать визуализацию самому, потому что попытка объяснить нечто — это лучший способ разобраться в предмете.

К тому же, графическое представление проблемы помогает найти ошибки в своей реализации алгоритма, да и вообще, это интересно само по себе.

Автор опубликовал анимационное представление следующих алгоритмов и процессов:

Тасование (shuffling)
Быстрая сортировка
Сортировка слиянием
Генерация лабиринтов (maze generation)
Дискретизация

Например, для быстрой сортировки Майк Босток предлагает три варианта визуализации: 1) анимация; 2) плотная стационарная экспозиция и 3) разреженная стационарная экспозиция. У каждого из вариантов есть свои преимущества и недостатки. Так, на анимацию интересно смотреть, зато статичные картинки можно вдумчиво изучить в подробностях.

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

function quicksort(array, left, right) {
  if (left < right - 1) {
    var pivot = (left + right) 9>> 1;
    pivot = partition(array, left, right, pivot);
    quicksort(array, left, pivot);
    quicksort(array, pivot + 1, right);
  }
}

function partition(array, left, right, pivot) {
  var pivotValue = array[pivot];
  swap(array, pivot, --right);
  for (var i = left; i < right; ++i) {
    if (array[i] < pivotValue) {
      swap(array, i, left++);
    }
  }
  swap(array, left, right);
  return left;
}

Два варианта статичной визуализации.