ソートアルゴリズムの可視化アニメーションが作りたくなって

はじめに

YouTubeを見ているとたまにこういう、ソートアルゴリズムの動作を可視化するアニメーション動画が流れてくる。

www.youtube.com

こういうのはHTML/JavaScriptだとどうやって作るんだっけな、ということで作ってみた。配列の要素が入れ替わるのに対応して、画面中のバーが入れ替わる、という形を目指す。

基本的なアイデア

配列に対してソートアルゴリズムを実行しつつ、並列してDOM要素や属性値を入れ替える、みたいなことを考えたくなるけど、普通にソートアルゴリズムを実装すると人間には見えない速さで終わってしまう。10万要素の配列を Array.prototype.sort メソッドでソートしたら、普通は1秒もかからず終わるだろう。

ソートを実行しつつ、配列の要素を入れ替えた直後にDOM要素を書き換える余地がほしい。言い換えると、配列の要素を入れ替えた瞬間にソートを中断し、DOM要素の入れ替えが終わるぐらいの時間待ってからソートを再開したい。どうやって？

結論から言うと、ジェネレータ関数を使うことで実現できる。ソートアルゴリズムをジェネレータ関数で実装しつつ、配列の要素を入れ替えた直後に yield 演算子でジェネレータの呼び出し元に処理を戻してきて、DOM要素を入れ替える、という形に整理する。setInterval 関数を使って適当な時間間隔ごとにジェネレータを進めて、ジェネレータが完了するまで回してあげればいい。

実装

雰囲気はだいたいこういう感じ。

// 入れ替え対象の配列を初期化する
let arr = arrayToShuffled(new Array(120).fill(0).map((_, i) => i));

function* swap(i: number, j: number) {
  [arr[i], arr[j]] = [arr[j], arr[i]];
  yield;
}

function* bubbleSort() {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      if (arr[j] < arr[j + 1]) {
        yield* swap(j, j + 1);
      }
    }
  }
}

const gen = bubbleSort();
let swapCount = 0;
const timer = window.setInterval(() => {
  swapCount++;
  const { done } = gen.next();
  // ここでDOM要素を書き換える
  if (done) {
    console.log(`finished with ${swapCount} swaps`);
    window.clearInterval(timer);
  }
}, 1000 / 120);

yield* 演算子を使うことで他のジェネレータに処理を移譲できる。これによって swap 関数のようなヘルパーを作れるし、マージソートのような再帰を伴うアルゴリズムも実装しやすくなる。

できたもの

リポジトリはこれです。Reactを使いつつ無理やり useSyncExternalStore フックで値を同期しているのがかわいらしいポイントです。

github.com

https://sugarheart.utgw.net/sort-animation/ にアクセスしてクエリパラメータでいくらか調整できます。

n: 要素数
algorithn: ソートアルゴリズム。この記事を書いた時点では以下のいずれかに対応しています。デフォルトは bubble です
- bubble: バブルソート
- shaker: シェーカーソート
- insertion 挿入ソート
- merge: マージソート

動作例

Webページなのでiframeで埋め込めます。こうやって見るとバブルソートって遅いんですね。

バブルソート (N=200)

シェーカーソート (N=200)

挿入ソート (N=200)

マージソート (N=1000)

おわりに

ソートアルゴリズムの可視化アニメーションをどうやって作るのか、疑問が解決できたのでよかった。普段あまりジェネレータを使って暮らしておらず、Promiseによる非同期処理とはまた異なるパラダイムにちょっと足を踏み入れることができたんじゃないか。ジェネレータの中で再帰したいけどどうすれば……と思っていたら yield* 演算子で解決できることを知ったあたりでだいぶ前進した。

クイックソートを実装しようとしたけどうまく書けず断念したので、今後の課題とします。

いろいろなソートアルゴリズムを実装してランダムなスクリーンセイバーにしたいな～。

私が歌川です

@utgwkk が書いている