通し番号のついた画像の束を、別の順番に並べ替えたい場面があります。

1.png から 7.png まで並んでいて、これを「5番を先頭へ持ってきて、残りを1つずつ後ろへずらす」といった具合に組み替えたい。素直にやるなら、新しい順番でファイルを全部コピーし直せば終わりです。

ただ、枚数が多かったり1枚が重かったりすると、コピーは時間も容量も食います。中身は1バイトも変わらないのに、です。動かしたいのは「順番」だけ。だったら、ファイル名（通し番号）を付け替えるリネームだけで並べ替えたい。

この記事では、そのリネームの順番をどう決めるかを考えます。素朴なスワップ方式と、少し賢い玉突き方式（循環置換）を比べて、同じ並び替えでも手数がどれだけ変わるかを、最後にブラウザだけで動くビジュアライザで実際に触って確かめます。

まず、リネームには落とし穴がある

「1番には今の5番の画像を、2番には今の1番の画像を…」と指示があったとして、思いつくまま 5番→1番 のように上書きリネームしていくと、すぐに事故が起きます。

2をそのまま1へ上書きリネームすると、元の1の画像が消えてしまう様子

上書きされた先の画像は、その瞬間に消えます。並び替えのつもりが、画像の破壊になってしまう。

これを避けるには、動かす1枚をいったん別の場所（temp）に逃がしてから動かします。逃がした跡地には**「穴」**が空きます。実は、この穴をどう埋めていくかが戦略の分かれ道です。

ここからは説明をシンプルにするため、7枚の画像にそれぞれ A〜G の中身が入っているとして話を進めます。スロット 1 には A、2 には B…という初期状態です。

並び替えの指示は、"並び先スロット": "元スロット" という対応表で表します。

{
  // 5番(E)を先頭へ。1〜5を1つずつ後ろへずらし、6番(F)と7番(G)は入れ替え
  "1": "5",   // 1番には 元5(E) を持ってくる
  "2": "1",
  "3": "2",
  "4": "3",
  "5": "4",
  "6": "7",
  "7": "6"
}

値（右側）が 1〜7 を1回ずつ全部使っていれば、画像が消えも増えもしない正しい並び替えです。重複や抜けがあれば、それは「同じ画像を2か所へ」「どこにも置かれず消える画像がある」というバグなので、実行前に弾きます。

素朴なやり方：スワップ方式

いちばん分かりやすいのは、1番から順番に定位置を埋めていくやり方です。

スロット 1 を見て、「ここに来るべき画像は今どこにあるか」を調べ、そこと交換する。次に 2 を見て…と、番号順に確定させていきます。「ここに来るべき画像が今どこか」は、画像の現在地を覚えておく loc という表で追跡します。

問題は、1回の交換にリネームが3回かかることです。temp に逃がして、欲しい画像を運んで、temp の中身を空いた場所へ戻す。これで3手です。

スロット1と6を入れ替えるのに、temp退避・運ぶ・戻すの3手かかる図

番号順に処理するので追いやすい反面、交換のたびに必ず temp への往復が発生します。交換が増えるほど、この「3手」がそのまま積み上がっていきます。

少し賢いやり方：玉突き方式（循環置換）

玉突き方式は、並び替えを最初に**鎖（サイクル）**として捉え直します。

さっきの指示を「誰が誰の場所を欲しがっているか」で辿ると、1→5→4→3→2 と一本の鎖になります。「1番が欲しいのは5番の画像、5番が欲しいのは4番の画像、4番が欲しいのは3番…」と繋がって、最後は2番が1番の画像を欲しがって輪が閉じます。6 と 7 はお互いを欲しがる、長さ2の短い鎖です。

鎖さえ作れれば、あとは穴を歩かせるだけです。

鎖1→5→4→3→2の上を穴が一歩ずつ歩き、tempのAを最後に戻して完了する図

  1. 鎖の先頭の1枚（A）を temp へ逃がす。そこに穴が空く。
  2. 今ある穴に「そこへ入るべき1枚」を運ぶ。運んだ跡地が次の穴になる。
  3. これを繰り返すと、穴が鎖の上を一歩ずつ歩いていく。最後に temp の1枚を戻して、その鎖は完了。

ポイントは、穴に入った画像はそのまま最終位置だということです。一度置いたら二度と動かしません。スワップ方式のように毎回 temp へ往復しないので、temp を使うのは1つの鎖につき1回だけで済みます。

番号順ではなく穴の位置に従って動くので、「2 より先に 4 を触る」ように見えますが、それはその時点の穴が 4 の画像を欲しがっているからです。順番が飛んで見えても、ちゃんと筋は通っています。

なぜ玉突きが速いのか

手数を式にすると、違いがはっきりします。

  • 玉突き方式：動いた画像の枚数 ＋ 鎖の本数。長さ $n$ の鎖は $n+1$ 手（先頭を逃がす1手＋戻す1手を含む）。
  • スワップ方式：互換数 × 3。長さ $n$ の鎖をほどくには $n-1$ 回の交換が要り、1交換が3手。

先ほどの指示（長さ5の鎖＋長さ2の鎖）で数えると、こうなります。

同じ並び替えに必要なリネーム回数の比較。サンプルは玉突き9回・スワップ15回、先頭挿入は玉突き8回・スワップ18回

長さ5の鎖は玉突きなら 5＋1＝6 手、スワップなら 4交換×3＝12 手。長さ2の鎖はそれぞれ3手ずつ。合わせて玉突き9手、スワップ15手です。

「全部を1つずつ後ろへずらす」先頭挿入（長さ7の1本鎖）だと差はもっと開いて、玉突き8手 vs スワップ18手になります。鎖が長いほど、temp 往復のコストが効いてくるわけです。

逆に、単純な2枚入れ替え（長さ2の鎖）だけなら、どちらも3手で並びます。差がつくのは鎖が長いときだけ、というのも正直なところです。

触ってみる

ここまでの話を、実際に動かして確かめられるようにしました。下のビジュアライザはサーバー不要、このページの中だけで完結して動きます。

  • 上の方式を「玉突き／スワップ」で切り替えると、同じ並び替えでの手数の差がそのまま見えます。
  • 「最初から再生」で1ステップずつ自動再生。temp・穴・確定（緑枠）の様子を追ってみてください。
  • 下の「並び順を自分でいじる」を開くと、プリセットを選んだり JSON を手で書き換えたりできます。番号の重複・抜けはその場で赤く弾きます。

うまく表示されないときは、ビジュアライザを別タブで開く 。

実装の要点

中心になるのは3つだけです。

まず、指示が正しいか検査する。 手で書いた対応表には、番号の重複や抜けが紛れ込みます。並び先と元が両方とも 1〜7 を1回ずつ使う「全単射」かどうかを、実行前に必ず確認します。ここを通さないと、画像が消えるバグをそのまま実行してしまいます。

次に、鎖を見つける。 1番から順に走査して、まだ触っていないスロットを起点に鎖を辿ります。自分自身を指すスロット（不動点）は動かす必要がないので飛ばします。

function planCycles(perm){
  const visited = new Set(), cycles = [];
  for(const start of SLOTS){
    // 不動点・処理済みは飛ばす
    if(visited.has(start) || perm[start] === start){ visited.add(start); continue; }
    const cyc = [start]; visited.add(start);
    let j = start;
    // 出発点に戻るまで鎖を辿る
    while(perm[j] !== start){ j = perm[j]; cyc.push(j); visited.add(j); }
    cycles.push(cyc);
  }
  return cycles;
}

最後に、鎖ごとに穴を歩かせる。 先頭を temp へ逃がし、穴に入るべき画像を順に運び、最後に temp を戻します。

function buildOpsCycle(perm){
  const cycles = planCycles(perm);
  const ops = [];
  for(const cyc of cycles){
    const head = cyc[0];
    ops.push({ src: head, dst: "temp" });          // 先頭を退避＝穴ができる
    for(let k = 0; k < cyc.length - 1; k++){
      ops.push({ src: cyc[k+1], dst: cyc[k] });     // 穴に「入るべき1枚」を運ぶ
    }
    ops.push({ src: "temp", dst: cyc[cyc.length-1] }); // 最後に temp を戻す
  }
  return ops;
}

あとはこの ops（リネーム手順）を上から順に実行するだけです。サムネイル用の縮小画像が別にあるなら、同じ手順をそちらにも適用すれば、原本とサムネの並びがズレません。

ここでは踏み込まない点

きれいに見えて、現場に出すなら詰めるべき穴もあります。

  • 中断耐性。リネームの途中でクラッシュすると、中途半端な並びが残ります。本番では「作業ディレクトリを丸ごと差し替える」か「手順を記録しておいて復旧できるようにする（ジャーナル）」あたりを別途考える必要があります。
  • 追加と削除。この記事は「枚数が変わらない純粋な並び替え」に絞りました。新しい画像を足したり、途中の画像を消したりは、また別の設計の話になります（並び替え本体とは分けて考えるのが素直です）。

まとめ

  • 通し番号つきの画像は、コピーしなくてもリネームだけで並べ替えられる。ただし上書きで画像が消えるので、temp への退避が要る。
  • スワップ方式は1番から定位置を埋める素直なやり方。分かりやすいが、1交換ごとに temp 往復で3手かかる。
  • 玉突き方式は並び替えを鎖として捉え、穴を歩かせる。temp は鎖あたり1回、動いた画像は最終位置へ直行するので、手数が最小になる。
  • 差がつくのは鎖が長いとき。短い入れ替えだけなら大差はないが、全体がぐるりとずれるような並び替えほど、玉突きが効いてくる。

理屈だけだとピンと来にくいので、ぜひ上のビジュアライザでプリセットを切り替えながら、穴が歩く様子を眺めてみてください。