画像を「リネームだけ」で並び替える。玉突き方式とスワップ方式、手数はどれだけ違うか
通し番号のついた画像の束を、別の順番に並べ替えたい場面があります。 1.png から 7.png まで並んでいて、これを「5番を先頭へ持ってきて、残りを1つずつ後ろへずらす」といった具合に組み替えたい。素直にやるなら、新しい順番でファイルを全部コピーし直せば終わりです。 ただ、枚数が多かったり1枚が重かったりすると、コピーは時間も容量も食います。中身は1バイトも変わらないのに、です。動かしたいのは「順番」だけ。だったら、ファイル名（通し番号）を付け替えるリネームだけで並べ替えたい。 この記事では、そのリネームの順番をどう決めるかを考えます。素朴なスワップ方式と、少し賢い玉突き方式（循環置換）を比べて、同じ並び替えでも手数がどれだけ変わるかを、最後にブラウザだけで動くビジュアライザで実際に触って確かめます。 まず、リネームには落とし穴がある 「1番には今の5番の画像を、2番には今の1番の画像を…」と指示があったとして、思いつくまま 5番→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手です。 番号順に処理するので追いやすい反面、交換のたびに必ず temp への往復が発生します。交換が増えるほど、この「3手」がそのまま積み上がっていきます。 少し賢いやり方：玉突き方式（循環置換） 玉突き方式は、並び替えを最初に鎖（サイクル）として捉え直します。 さっきの指示を「誰が誰の場所を欲しがっているか」で辿ると、1→5→4→3→2 と一本の鎖になります。「1番が欲しいのは5番の画像、5番が欲しいのは4番の画像、4番が欲しいのは3番…」と繋がって、最後は2番が1番の画像を欲しがって輪が閉じます。6 と 7 はお互いを欲しがる、長さ2の短い鎖です。 鎖さえ作れれば、あとは穴を歩かせるだけです。 鎖の先頭の1枚（A）を temp へ逃がす。そこに穴が空く。 今ある穴に「そこへ入るべき1枚」を運ぶ。運んだ跡地が次の穴になる。 これを繰り返すと、穴が鎖の上を一歩ずつ歩いていく。最後に temp の1枚を戻して、その鎖は完了。 ポイントは、穴に入った画像はそのまま最終位置だということです。一度置いたら二度と動かしません。スワップ方式のように毎回 temp へ往復しないので、temp を使うのは1つの鎖につき1回だけで済みます。 ...
