GODRICH
#cssアニメーション#ボタン#ローディング#トランジション#スクロール#ダッシュボード#実用ui#デザイントレンド

ソート アルゴリズム 可視化 9種 — 隣と入れ替わる棒から色相環を回して並べる円形ソートまで

· Godrich · 9種 · 14分で読める

game素のJSSCSS自動再生ゲーム・遊びポートフォリオヒーロー

並べ替えはコードを読んでも覚えにくく、動きで見ると分かります。04番は基準の棒を立てて両側へ掃き分け、07番は同じ配列で四つの方法の比較回数を競わせ、06番は色の片を色相環の順に回して並べます。ソート アルゴリズム 可視化 9種は、実際に並べ替えを動かして手順の一覧を作り、一歩ずつ再生します。

並べ替えは値ではなく動きで理解します — ソート アルゴリズム 可視化は棒の高さを値にして、比較と交換を一歩ずつ描くところから始まります

隣の棒が入れ替わるバブルソートの棒の軌跡01 srt-bubble-bar-swap-trace 一本を持ち上げてちょうどよい隙間にはさむ挿入ソート02 srt-insertion-lift-slot 半分に割って二列を編み合わせる併合ソート03 srt-merge-split-weave 基準の棒を立てて両側へ掃き分けるクイックソート04 srt-quick-pivot-partition-sweep 二分木の上で大きな値を下ろしていくヒープソート05 srt-heap-tree-sift-down ばらばらの色片を色相環の順に回して並べる円形ソート06 srt-hue-circle-color-sort 同じ配列で四つの方法の比較・移動回数を競わせるレースメーター07 srt-compare-count-race-meter 桁の数字ごとの箱に流し込んで集め直す基数ソート08 srt-radix-bucket-pour 崩れた街のシルエットがひとりでに整って階段になるヒーロー09 srt-hero-skyline-self-sort

自動再生 · タイルを押すとその項目へ · すべて1つのzip

九つの場面は同じ決まりで作りました。並べ替えを本当に一回動かして、比較・交換・書き込みといった一歩を一覧に記録しておき、画面はその一覧を時間表どおりに一つずつ読んで描きます。棒の高さもカウンターの数字も適用した一歩からだけ出るので、画面が見せているのは演出ではなく計算された並べ替えの過程です。

棒を描く側と並べ替える側を分けた理由

並べ替える側は bubbleSteps・mergeSteps・quickSteps のように配列を受け取って手順の一覧を返す純粋な関数で、描く側はその一覧を受け取って適用するだけです。だからソート アルゴリズム 可視化 ツールの動きを変えたいときは、棒を描くコードはそのままにして手順を作る関数だけを差し替えれば済みます。07番はこの仕組みを四つ重ねて、同じ配列から別々の手順の一覧四本を同時に再生します。

音ではなく棒の高さで読みます

並べ替えを音で聞かせる ソート アルゴリズム 可視化 サイトを探してきた人もいるかもしれませんが、この記事はオーディオを使わず、棒の高さとカウンターの文で値を伝えます。

場面ごとに足した計算ひと手間

01番はばねの交換と残像、02番は低い振動数のばねによる慣性、03番は層ごとの曲線の飛行、04番は基準の高さの点線を足しました。05番は木と棒を同時に見せ、06番は色相環の片を回し、07番は四本のレーンの比較と移動の回数をメーターに立てます。08番は重力と床での跳ね返り、09番は進行率にしたがって明るくなる空を足しました。

ソート アルゴリズム 可視化 9種 — 隣と入れ替わるバブルの棒・隙間にはさむ挿入・半分に割って編む併合・基準を立てて掃き分けるクイック・木で下ろすヒープ・色相環を回す円形・四つの方法を競わせるメーター・箱に流し込む基数・ひとりでに整う街のシルエット

九つの場面を描いて測った面積・フレーム・強さ

場面 累積面積 動いたフレーム 強さの平均
01 バブルの棒 29.6% 23/23 66.6
02 挿入 25.5% 23/23 65.8
03 併合 10.0% 23/23 84.7
04 クイック 22.6% 22/23 52.8
05 ヒープ 11.9% 22/23 60.9
06 色相環 14.8% 21/23 52.3
07 レースメーター 12.7% 23/23 76.4
08 基数 28.3% 23/23 60.3
09 街のシルエット 70.8% 23/23 61.2

空とビルの全体が変わる09番の70.8%がいちばん広く、層に分かれた列の一部だけが変わる03番の10.0%がいちばん狭くなりました。強さの平均は03番の84.7が最大で06番の52.3が最小です。04番・05番は22/23、06番は21/23なので、この三つの場面には変化のないフレームがまじっています。

01隣の棒が入れ替わるバブルソートの棒の軌跡

並べ替えの学習サイトの最初の画面に置くと、入れ替わる二本が互いの場所をわたる場面がすぐ目に入ります。bubbleSteps が作った手順のうち交換（SWP）の一歩だけが row 配列を本当に入れ替え、画面の sx は spr のばねで新しい場所を追いかけます。右へわたる棒は lift で少し浮いて向かってくる棒と重ならず、通った跡には TRAIL_S のあいだうすい残像が残ります。

隣の棒が入れ替わるバブルソートの棒の軌跡
新しいタブで開く

01 · 隣の棒が入れ替わるバブルソートの棒の軌跡 — 計測 累積面積 29.642% · 動いたフレーム 23/23GODRICH オリジナル · SCSS と React は zip に同梱 · パスワードを見る

BAR_COUNTSWAP_TRAVEL_MSbubbleSteps
    function update(dt) {
        trailClock += dt;
        for (let p = 0; p < BAR_COUNT; p += 1) {
            const id = row[p];
            spr(sx[id], slotX(p), dt, SPRING_W, SPRING_Z);
            // 右へわたる棒は少し浮き上がり、わたってくる棒と重ならない
            const away = slotX(p) - sx[id].x;
            spr(lift[id], away > 1 ? -Math.min(14, away * 0.35) : 0, dt, 22, 0.8);
            flash[id] = Math.max(0, flash[id] - dt * 2.4);
            const tr = trails[id];
            for (const t of tr) {
                t.age += dt;
            }
            while (tr.length > 0 && tr[0].age > TRAIL_S) {
                tr.shift();
            }
            if (Math.abs(slotX(p) - sx[id].x) > 2.5 && trailClock > 0.012) {
                tr.push({ x: sx[id].x, y: lift[id].x, age: 0 });
            }
        }
        if (trailClock > 0.012) {
            trailClock = 0;
        }
    }

02一本を持ち上げてちょうどよい隙間にはさむ挿入ソート

カードの整理や優先順位リストの並べ替え画面で見かける挿入ソートです。LIFT の一歩が棒を一本 LIFT_H だけ持ち上げ、左の大きい棒は SHF の一歩ごとに一つずつずれ、DROP が空いた隙間へ下ろします。ずれる棒は SHIFT_W が19の低い振動数のばねなので場所に少し遅れてつき、持ち上げた棒は34で隙間の上をより速く追います。

一本を持ち上げてちょうどよい隙間にはさむ挿入ソート
新しいタブで開く

02 · 一本を持ち上げてちょうどよい隙間にはさむ挿入ソート — 計測 累積面積 25.461% · 動いたフレーム 23/23GODRICH オリジナル · SCSS と React は zip に同梱 · パスワードを見る

LIFT_HSHIFT_WinsertionSteps
    function update(dt) {
        for (let p = 0; p < BAR_COUNT; p += 1) {
            if (row[p] >= 0) {
                spr(sx[row[p]], slotX(p), dt, SHIFT_W, SHIFT_Z);
            }
        }
        for (let id = 0; id < BAR_COUNT; id += 1) {
            if (id === liftId) {
                spr(sx[id], slotX(holeAt), dt, 34, 0.7);
            }
            spr(ly[id], id === liftId ? -LIFT_H : 0, dt, 30, 0.6);
        }
    }

03半分に割って二列を編み合わせる併合ソート

二つの一覧を日付順に合わせる機能を説明するときに合う併合ソートです。SPLIT の一歩四回が五つの層（LEVELS）を順に開き、合わせるときは CMP で二列の先頭を比べて小さいほうを SET で上の層へ書きます。書かれた棒は FLY_S のあいだ二点のあいだを曲線で飛び、曲線の制御点は二つの場所より26px上にあります。

半分に割って二列を編み合わせる併合ソート
新しいタブで開く

03 · 半分に割って二列を編み合わせる併合ソート — 計測 累積面積 10.017% · 動いたフレーム 23/23GODRICH オリジナル · SCSS と React は zip に同梱 · パスワードを見る

FLY_SLEVELSmergeSteps
        // 飛ぶ棒 — 下の層の場所から上の層の場所へ、上に膨らむ曲線
        for (const f of flights) {
            const k = ease(f.t);
            const mx = (f.x0 + f.x1) / 2;
            const my = Math.min(f.y0, f.y1) - 26;
            const x = (1 - k) * (1 - k) * f.x0 + 2 * (1 - k) * k * mx + k * k * f.x1;
            const y = (1 - k) * (1 - k) * f.y0 + 2 * (1 - k) * k * my + k * k * f.y1;
            drawBar(x + 2, y, f.v, 1, true);
        }

04基準の棒を立てて両側へ掃き分けるクイックソート

検索結果を速く分けて並べる過程を説明するのに向いたクイックソートです。区間の先頭の棒が PIV の一歩で PIVOT_LIFT だけ持ち上がって基準になり、二つのポインタが向かい合って掃きながらずれた組を交換し、出会ったら基準を下ろします。基準の棒の上面の高さには区間の幅だけ点線が引かれ、ポインタが比べる目盛りになります。

基準の棒を立てて両側へ掃き分けるクイックソート
新しいタブで開く

04 · 基準の棒を立てて両側へ掃き分けるクイックソート — 計測 累積面積 22.576% · 動いたフレーム 22/23GODRICH オリジナル · SCSS と React は zip に同梱 · パスワードを見る

PIVOT_LIFTSWAP_MSquickSteps
        // 基準の高さの点線 — ポインタはこの線と棒の上面を比べる
        if (pivId >= 0) {
            const py = BASE_Y - barH(vals[pivId]);
            ctx.setLineDash([5, 4]);
            ctx.lineWidth = 1.5;
            ctx.strokeStyle = rgba(INK, 0.5);
            ctx.beginPath();
            ctx.moveTo(slotX(rangeLo), py);
            ctx.lineTo(slotX(rangeHi + 1), py);
            ctx.stroke();
            ctx.setLineDash([]);
        }

05二分木の上で大きな値を下ろしていくヒープソート

優先度つきキューで作業を取り出すスケジューラを説明するときに使うヒープソートです。同じ値が木の節と棒の列の二か所にあって線で結ばれ、位置ごとに tx・ty・bx の三つのばねが別々に追うので、節が木を下りるあいだ棒も列の中でいっしょに動きます。木の場所は treeX が層ごとに2^l 個の区画へ幅を等分して決めます。

二分木の上で大きな値を下ろしていくヒープソート
新しいタブで開く

05 · 二分木の上で大きな値を下ろしていくヒープソート — 計測 累積面積 11.944% · 動いたフレーム 22/23GODRICH オリジナル · SCSS と React は zip に同梱 · パスワードを見る

COUNTtreeXheapSteps
    // 位置 p の木の座標 — 層 l は 2^l 個の区画に幅を等分する
    function treeX(p) {
        const l = Math.floor(Math.log2(p + 1));
        const k = p + 1 - Math.pow(2, l);
        return (W / Math.pow(2, l)) * (k + 0.5);
    }
    function treeY(p) { return 64 + Math.floor(Math.log2(p + 1)) * 34; }
    function barX(p) { return 21 + p * 29.5 + 12; }

06ばらばらの色片を色相環の順に回して並べる円形ソート

カラーパレットの並べ替えツールや背景の飾りに使える円形ソートです。色相の値が円のまわりの片になり、selectionSteps が残りの区間の最小値を探して入れ替えますが、この探すだけで比較が276回あります。入れ替わる片は場所から離れた角度に応じて popOf が最大 RING_POP の24pxまで内側へ入れるので、わたっているあいだだけ輪からずれて見えます。

ばらばらの色片を色相環の順に回して並べる円形ソート
新しいタブで開く

06 · ばらばらの色片を色相環の順に回して並べる円形ソート — 計測 累積面積 14.782% · 動いたフレーム 21/23GODRICH オリジナル · SCSS と React は zip に同梱 · パスワードを見る

RING_POPpopOfselectionSteps
    // 片が自分の場所から離れた角度に比例して内側へ入る — わたっている間だけ飛び出して見える
    function popOf(id, p) {
        return RING_POP * ease(Math.abs(wrapPi(slotAngle(p) - ang[id].x)) / 0.6);
    }
    function update(dt) {
        for (let p = 0; p < COUNT; p += 1) {
            const id = row[p];
            const target = ang[id].x + wrapPi(slotAngle(p) - ang[id].x);
            spr(ang[id], target, dt, SPRING_W, SPRING_Z);
        }
    }

07同じ配列で四つの方法の比較・移動回数を競わせるレースメーター

アルゴリズム選びのガイドにある性能比較を目で見せるメーターです。同じ14個の配列をバブル・挿入・併合・クイックの四本のレーンに写し、STEP_MS ごとに一歩ずつ同時に適用して、レーンごとに cnt.c（比較）と cnt.m（移動）を上げます。数えるのは laneStep の一か所だけで、比較・交換・ずらし・書き込みを適用した一歩からだけ数え、標識の一歩は時間を使わずに通り過ぎます。

同じ配列で四つの方法の比較・移動回数を競わせるレースメーター
新しいタブで開く

07 · 同じ配列で四つの方法の比較・移動回数を競わせるレースメーター — 計測 累積面積 12.707% · 動いたフレーム 23/23GODRICH オリジナル · SCSS と React は zip に同梱 · パスワードを見る

STEP_MScountOfapplyLane
    function laneStep(l, s) {
        if (s.k === CMP) {
            cnt[l].c += 1;
            hot[l] = [s.a, s.b];
        }
        else if (s.k === SWP || s.k === SET || s.k === MOV || s.k === SHF) {
            cnt[l].m += 1;
            hot[l] = [s.a, s.b];
        }
        else if (s.k === FIX) {
            sortedFx[l][s.a] = true;
        }
        applyLane(lanes[l], s);
    }

08桁の数字ごとの箱に流し込んで集め直す基数ソート

郵便番号や社員番号のように桁のある値を仕分ける場面に合う基数ソートです。radixSteps が桁ごとに DRP で玉を箱へ流し込み、TAK で0番の箱から取り出すので、値どうしの比較は一度もありません。落ちる玉は GRAVITY の900px/秒²で加速し、床に着いたとき速さが70px/秒を超えていれば BOUNCE の0.38倍で跳ね上がります。

桁の数字ごとの箱に流し込んで集め直す基数ソート
新しいタブで開く

08 · 桁の数字ごとの箱に流し込んで集め直す基数ソート — 計測 累積面積 28.308% · 動いたフレーム 23/23GODRICH オリジナル · SCSS と React は zip に同梱 · パスワードを見る

GRAVITYBOUNCEradixSteps
            if (b.mode === 1) {
                b.vy += GRAVITY * dt;
                b.y += b.vy * dt;
                if (b.y >= ry) {
                    b.y = ry;
                    if (b.vy > 70) {
                        b.vy = -b.vy * BOUNCE;
                    }
                    else {
                        b.vy = 0;
                        b.mode = 2;
                    }
                }
            }

09崩れた街のシルエットがひとりでに整って階段になるヒーロー

開発者向け教育サービスのランディングの最初の画面にのせるヒーロー場面です。hybridSteps が四つずつの組は挿入で、組どうしは併合でビルを動かし（MOV）、空の sky は at / 歩数 で進行率を一つの値にまとめて、夜の色から明け方の色・星・太陽がその値を追います。窓の灯りがついたまま背の順の階段のシルエットが整うと一回分が終わります。

崩れた街のシルエットがひとりでに整って階段になるヒーロー
新しいタブで開く

09 · 崩れた街のシルエットがひとりでに整って階段になるヒーロー — 計測 累積面積 70.819% · 動いたフレーム 23/23GODRICH オリジナル · SCSS と React は zip に同梱 · パスワードを見る

RUNMOVE_MShybridSteps
        const t = ease(clamp(sky.x, 0, 1));
        skyFill(mix(NIGHT_TOP, DAWN_TOP, t), mix(NIGHT_BOT, DAWN_BOT, t));
        // 星 — 整列が進むほど消える
        for (const st of stars) {
            const a = clamp(1 - t * 1.5, 0, 1) * (0.5 + 0.5 * Math.sin(sceneT * 1.4 + st[3] * TAU));
            disc(st[0], st[1], st[2], PAPER, a * 0.85);
        }
        // 太陽 — 進行率にしたがって下から上がる
        const sy = lerp(318, 112, t);
        disc(388, sy, 62, SUN, 0.18 * t);
        disc(388, sy, 40, SUN, 0.3 * t);
        disc(388, sy, 24, SUN, 0.95 * Math.min(1, t * 1.6));

ソート アルゴリズム 可視化は棒が何本、一歩が何ミリ秒なら読めるのでしょうか？

授業で黒板のかわりに使うとき

データ構造の授業では同じアルゴリズムを何度か戻して見ることが大切なので、一時停止と一歩ボタンが役に立ちます。クイックソートは04番のように基準の棒がどこに下りるかを一歩ずつ確かめられる必要があり、STEP_MS を75、棒を18本にしました。再生を止めて一歩ずつ進めるとカウンターもその一歩までしか上がらないので、生徒が自分で数えた値と合わせられます。

面接の準備で手を動かして写すとき

面接の準備で並べ替えを覚えている途中なら、07番を流しておいて方法ごとに比較と移動がどう分かれるかを目で先に覚え、そのあと手で写す順番が楽です。07番の同じ14個の列を四本が受けたときと、各場面の最初の一回の実測は次の表のとおりです。

アルゴリズム 棒の数 比較 移動
07 バブル 14 90 交換 52
07 挿入 14 62 ずらし 52
07 併合 14 39 書き込み 54
07 クイック 14 38 交換 14
01 バブル 16 119 交換 56
02 挿入 14 59 ずらし 50
03 併合 16 44 書き込み 64
04 クイック 18 71 交換 16
05 ヒープ 15 72 交換 47
06 選択 24 276 交換 20
08 基数 24 0 流し込み 72・取り出し 72
09 混合 16 51 移動 23

同じ14個の列では、比較はバブルの90からクイックの38まで、移動はクイックの14から併合の54まで分かれます。棒の数がちがう行どうしは直接比べられず、06番の選択ソートは24個で比較を276回使うので、探す方式が比較をどれだけ使うかが分かります。08番は値どうしを比べず流し込みと取り出しだけなので、比較の欄は0です。

棒の数と一歩の間隔の目安

01番の比較回数は棒の数nに対してn(n−1)/2が上限で、16本では120、48本では1,128となり、実測は119と1,107です。棒の幅は (480−32)/n なので16本で28px、48本で約9pxになり、値の文字は幅が16px以上のときだけ描くため、棒を増やすと数字が消えます。一歩の間隔は一歩の種類ごとに別に置いてあり、比較が276回ある06番は SCAN_MS の18で短く探し、交換には420msを与えて、探すのは速く、交換は目に残るようにしました。

棒の列を作り、比較と交換を手順の一覧に記録し、一歩ずつ再生します — 並べ替え一つが目に見えるまでの順番です

画面とカウンターを一か所から出す理由は一つです。手順を作るときではなく適用するときに数えれば、一時停止・一歩進める・途中から始まる最初の場面のどれでも同じ数字が出ます。

一歩を適用するときだけ数えます

runOne が一歩を取り出して countStep で比較と移動を数え、applyOne で画面の状態を変えてから at を一つ上げます。比較は CMP、移動は SWP・SET・MOV・SHF で、確定の標識（FIX）や層を開く標識は数えません。

    function countStep(s) {
        if (s.k === CMP) {
            cmpN += 1;
        }
        else if (s.k === SWP || s.k === SET || s.k === MOV || s.k === SHF) {
            movN += 1;
        }
    }
    function isDone() { return at >= steps.length; }
    // いまの一歩の進み具合（0〜1）— 一歩が終われば 1
    function stepFrac() { return at < steps.length ? clamp(acc / stepDur(steps[at]), 0, 1) : 1; }
    function runOne() {
        const s = steps[at];
        countStep(s);
        applyOne(s);
        at += 1;
    }

時間表どおりに適用する再生器

advance は経過時間 acc が一歩の長さ stepDur を超えるたびに一歩ずつ適用します。一歩の長さは種類で決まり、03番では併合の始まり（MRG）が0.1秒ですが、07番だけは標識の一歩（isMeta）に時間を割り当てず飛ばします。一回分が終わると HOLD_S のあいだ完成した姿を見せて次の回へ進み、最初の回は START_FRAC の分だけ一歩を先に適用して、整列の途中の場面が最初の画面に出ます。

    function advance(dt) {
        sceneT += dt;
        if (at < steps.length) {
            acc += dt;
            while (at < steps.length && acc >= stepDur(steps[at])) {
                acc -= stepDur(steps[at]);
                runOne();
            }
        }
        else {
            holdT += dt;
            if (holdT >= HOLD_S) {
                lap += 1;
                begin();
            }
        }
        update(dt);
    }

画面の状態は交換の一歩で変わります

01番の applyOne は比較の一歩では強調する二つの場所だけを変え、交換の一歩でだけ row の二つの位置を本当に入れ替えて、確定の一歩で緑に固まる場所を記録します。棒が見せる順番はこの row からだけ出るので、画面と整列の結果がずれる道はありません。

    function applyOne(s) {
        if (s.k === CMP) {
            hiA = s.a;
            hiB = s.b;
        }
        else if (s.k === SWP) {
            swapAt(row, s.a, s.b);
            flash[row[s.a]] = 1;
            flash[row[s.b]] = 1;
            hiA = s.a;
            hiB = s.b;
        }
        else if (s.k === FIX) {
            fixedPos[s.a] = true;
        }
    }

並べ替えの可視化が壊れるのは、交換の途中の状態が画面に残って同じ値が二本に見える棒・手順の記録と再生がずれて整列が終わったのに棒が混ざっている画面・棒が数百本に増えて手順が一気に押し寄せる画面です

一つ目は、交換の途中で同じ値が二本に見える棒です。01番で row は交換の一歩で一度に変わりますが、画面の sx はばねで追うので二本が重なってすれちがううえ、残像も同じ高さで描くので、値が二つあるように読めます。残像は透明度0.34から始まって薄くなり、場所から遠い棒をあとで描いて本物の棒が残像の上に来るようにしました。

二つ目は、手順の記録と再生のずれです。カウンターを手順を作るときに上げると最初のフレームから合計が表示されて再生とずれるので、この記事は runOne の中でだけ上げます。一回分が終わったあとに一歩ボタンを押すと次の回を最初から開いて doneSaid を解き、新しい回の完了の知らせがもう一度出るようにしました。

三つ目は、手順が押し寄せる画面です。一歩の間隔がフレームの時間より短くなると一フレームに複数の一歩が入りますが、隠れていたタブが戻った最初のフレームは DT_MAX の0.05秒までしか計算せず、visibilitychange でループを止めてから再開して、隠れていた時間が一気に流れ込まないようにしました。

ソースの全体とライブ編集用のファイルは次のzipに入っていて、展開するパスワードは 7qbx64nu です。

棒の数と一歩の間隔を変えると方法の差はどれだけ開くのでしょうか — 列の長さ・再生の速さ・交換の移動時間を変えて比べます

名前 変えた値 感じ
棒を多く 01 BAR_COUNT 16 → 48 同じシードで比較は119回から1,107回、交換は56回から477回へそれぞれ約9倍に増え、全体の再生は約16秒から約139秒になります
一歩の間隔を短く 07 STEP_MS 90 → 30 いちばん長いバブルの列（142歩）が12.8秒から4.3秒に縮み、比較と移動の回数は変わりません
交換の移動を遅く 01 SWAP_TRAVEL_MS 160 → 420 ばねの固有振動数が37.5から約14.3rad/sに下がって棒が大きくゆれ、全体の再生は約16秒から約31秒になります

値を変える前に見ること

棒を48本に増やすと幅が約9pxに細くなって値の文字が消え、同じシードでも一回分が長くなって、一つの画面で最後まで見るには約139秒待つことになります。SWAP_TRAVEL_MS だけを上げても残像の保管時間 TRAIL_S は変わらないので、尾が移動経路より短く切れます。07番の STEP_MS を縮めても回数は同じなので、方法の差を見たいときは間隔ではなく棒の数を変えてください。

動きを減らす設定では整列済みの棒が一枚です — いまの手順を文で読み上げ、一歩ずつ進めるアクセシビリティです

整列完了の知らせは一度だけ

九つの場面はどれも時間表だけで最後まで進むデモで、ステージにフォーカスを置いてEnterかSpaceを押すと一時停止、右矢印キーは一歩進みます。一時停止ボタンは aria-pressed で押された状態を知らせ、整列が終わると隠した role="status" の行に完了の文を一度だけ書きます。

    let doneSaid = false;
    function checkDone() {
        if (isDone() && !doneSaid) {
            doneSaid = true;
            doneP.textContent = statusText();
        }
    }

キーボードと見えないタブ

    pad.addEventListener('keydown', function (e) {
        if (e.altKey || e.ctrlKey || e.metaKey) {
            return;
        }
        if (e.key === 'Enter' || e.key === ' ') {
            e.preventDefault();
            togglePause();
        }
        else if (e.key === 'ArrowRight') {
            e.preventDefault();
            stepOnce();
        }
    }, { signal: off.signal });

prefers-reduced-motion: reduce のときはループを動かさず、showRest が一歩を最後まで適用した整列完了の一枚だけを描いて、状態の行に「整列完了」の文を書きます。状態の行はデモ中は aria-live="off" にして一歩ごとに読み上げられないようにし、人が最初に触れると polite に変わります。

ソート アルゴリズム 可視化のよくある質問 — ライブラリなしで作る方法・整列できたかの確かめ方・利用者が入れた配列を使うときの限界

バブル ソート 可視化をライブラリなしで作れますか

キャンバス2Dだけで作れて、九つの場面すべてがライブラリ・WebGL・CDNを使っていません。乱数はシード固定の生成器 seeded で作るので、同じ入力から同じ手順の一覧ができ、並べ替えの関数はDOMを知らない純粋な関数なので、切り離してnodeで動かせます。

整列できたかどうかはどう確かめるのですか

手順の一覧を最後まで適用した配列を isSorted に渡せば分かり、この関数はソースに入っています。この記事を作るときにnodeで手順の生成器8個を動かして、すべて整列した結果になるのを確かめましたが、画面側のループはこの関数を呼びません。

利用者が入力した配列を入れてもいいですか

08番を除く場面が扱った入力は、1からnまでを一回ずつ入れた配列だけです。08番だけは三桁の数をもつ玉で、値は100から999までから重ならないように選びます。barH が値を棒の数で割って高さを作るため、同じ値が二つあったり負の数や大きな数が入ったりすると高さと色の計算から変える必要があり、棒を数百本に増やすと上の変形の表のとおり再生時間が長くなる限界も同時についてきます。

参考として、MDNのrequestAnimationFrameのページとCanvas 2Dのページ、動きを減らす設定はprefers-reduced-motionのページが基準です。棒が育つ仕組みが気になるなら棒グラフのばねの記事を、格子の上で道を探す場面は迷路ジェネレーターの記事を続けて見てください。

解凍パスワードを入力してください

パスワードはこの記事の本文の中にあります。読み進めると出てきます。