Silly Sort
湯淺 太一（京都大学大学院情報学研究科）
yuasa@kuis.kyoto-u.ac.jp

次章に進む前に，読者自身で例 2 〜例 4 の最小コス■問題

ト手順を考えてみてほしい．

2002 年の世界大会で出題された Silly Sort という問

■試行錯誤

題を取り上げる．整数の列が与えられたときに，2 つの整数を入れ換えることを繰り返して，昇順に（小さまず例 2 について考えよう．[8,1,2,4] をソートしていものから順に）並べ換えることを考える．ありふれ[1,2,4,8] にする．各整数の最終位置は，初期位置のすたソーティングだが，ソートに要するコストが少し変ぐ左隣である．ただし，先頭の整数は最後尾にまわる．

わっている．ステップ数ではなく，各ステップで入れそこで，すぐに思いつくのは，先頭の 8 を後ろの整数換える 2 つの整数の和を求め，その合計をコストとすと順に入れ換えていく手順であろう．
91012[8,1,2,4] →[1,8,2,4] →[1,2,8,4] →[1,2,4,8]る．たとえば，[3,2,1]

各ステップのコストを矢印の上に書いておく．コスをバブルソート風にトの合計は 31 となり，これは大きすぎる．

[3,2,1] →�[2,3,1] →�[2,1,3] →�[1,2,3][8,1,2,4] を図 -1 (a) に示すグラフで表現してみよう．と並べ換えると，コストはここで，○は整数列中の位置を表し，矢印は，始点の(32)(31)(12)12位置にある整数の最終位置が，終点の位置であることとなる．与えられた整数列を並べ換えるための最小のを表す．このグラフを見れば，なにもわざわざ大きなコストを求めるプログラムを作れ，というのが問題で8 を使ってソートしなくても，最小の 1 を使えばよさある．ただし，それぞれの整数は 1 以上 1000 未満とし，そうである．実際，整数は互いに異なるものとする．また，整数列の長さは１以上とする．

35
9[8,1,2,4] →[8,2,1,4] →[8,2,4,1] →[1,2,4,8]となって，コストは最小とされている 17 になる．

上の例の場合，最小コストが 4 であることはすぐにでは，どうして例 2 の最小コストが 17 なのだろう．

分かる．1 と 3 はソート完了時の最終位置にはないの

図 -1 (a) には，輪（循環構造）が 1 つある．上のステで，必ず１回は移動する必要があり，どのような手順ップを繰り返すと輪の本数が１ずつ増えていき（図 -1でソートしてもコストは 4 以上となる．そして，実際(b), (c)），最終的に輪が 4 つになる（図 -1 (d)）．一般に，にコストが 4 である手順が存在する．1 と 3 を入れ換

2 つの整数を入れ換えると，グラフ中の輪は１増加すえればよい．

る（同じ輪の整数を入れ換えるとき）か，１減少する（異問題文には，サンプル入力として次の 4 つの例が与なる輪の整数を入れ換えるとき）かのいずれかである

えられており，括弧内の値が最小コストとされている．

（図 -2 参照）．例 2 の場合は，最初は 1 つだった輪が，618

例 1: [3,2,1] (4)

最後は 4 つになるので，ソートするためには最低 3 回

例 2: [8,1,2,4] (17)のステップが必要である．いま，[8,1,2,4] を k 回 (k 

例 3: [1,8,9,7,6] (41)3) のステップでソートしたとすると，全部で 2k 個の例 4: [8,4,5,3,2,7] (34)整数を移動したことになる．最初は 8,1,2,4 のいずれ

45 巻 6 号情報処理2004 年 6 月��������������������������������������������������������������
図 -1��������������
図 -2

整数列のグラフ表現

輪の本数の増減（a と b を入れ換えると，それぞれのもとの位置から出ていた矢印は，終点は変わらないが始点が新しい位置に変わる）

も最終位置にはないので，それぞれ最低１回は移動す〈8,4,2,1〉 や 〈1,8,4,2〉 と表せ，σ(R)15，#(R)4，min(R)る．したがって，コストは

1 である．また，これらの記法を使えば，式 (1) は，σ(R)  (#(R)  2)  min(R)8124x1x2    x2k4と表せる．ここで，各 xi は 8,1,2,4 のいずれかである．と表せる．

このコストが最小になるのは，k3 かつ各 xi が最小与えられた整数列のグラフに複数の輪が存在するの 1 のときである．したがって，コストの最小値は，ときは，それぞれの輪に対して式 (1) を適用して合計を求めればよさそうである．実際，例 1 のグラフには，

812411172 つの輪 〈3,1〉 と 〈2〉 があり，式 (1) を使えばコストはとなる．
一般に，長さ n の整数列それぞれ 4 と 0 で，その和 4 が最小コストである．し[a1, a2,…, an]

かし例 3 については，そうはいかない．輪 〈8,7,9,6〉 のが与えられ，そのグラフに輪が 1 つしかないときは，コストを計算すると(8796)(42)642

コストの最小値はとなり，最小コストとされる 41 を上回る．どうやら，�� ��( � ��) ������ � �����������（1）となる．n  2 のとき，この式 (1) は，上の例 2 の場合とまったく同様に証明できる．n1 のとき，整数最初から最終位置にある 1 が曲者（くせもの）である．
コストが 42 になる手順（これを T1 とする）は次のとおりである．
15
1314[1,8,9,7,6] →[1,8,6,7,9] →[1,8,7,6,9] →[1,6,7,8,9]

列は最初からソート済みなので，コストは 0 である．

〈8,7,9,6〉 の最小値 6 を使ってソートするので，6 が 3

このとき，式 (1) の値も 0 となり，式 (1) は n1 のと回移動している．この 6 の代わりに，1 を使ってソーきにも適用できる．

トすることを考える．まず 1 と 6 を入れ換える．

以下では，〈a1, a2,…, an〉によって，整数 a1, a2,…, an から構成される輪を表すことにする．各 ai の最終位置が，1 つ後ろの ai1の位置である．また，輪 R に対して，それを構成する整数の和を σ(R)，個数を #(R)，最小値を min(R) と表記することにする．たとえば，図 -1 (a) の輪 R は

7[1,8,9,7,6] →[6,8,9,7,1]

その後，手順 T1 の各ステップで 6 の代わりに 1 を使ってみる．
108
9[6,8,9,7,1] →[6,8,1,7,9] →[6,8,7,1,9] →[6,1,7,8,9]

最後に，1 をもとの位置に戻せば，ソートが完了する．
7[6,1,7,8,9] →[1,6,7,8,9]

手順 T1 と比べると，最初に 1 を借りてくるコストとIPSJ Magazine Vol.45 No.6 June 2004619

最後に 1 を戻すコストが増えるが，手順 T1 の各ステ

• 整数列の最小値 s を輪 R が最初から含んでいる場

ップで 6 の代わりに 1 を使った分だけコストが減少す

合は，R の外部から整数を借りてくるより，R 内のる．その結果，総コストは最小とされる 41 になる．

入れ換えだけでソートした方がよい．

一般に，輪 R〈a1, a2,…, an〉 を，輪の外にある整数• 輪 R の外部から整数を 1 つ借りてきてソートする

x を使って上のようにソートする場合，コストは次のなら，最小値 s を借りるのがよい．その際に，s とように表せる．

入れ換える R の要素としては，R の最小値 min(R)

σ(R)  (#(R) 2)  min(R)がベストである．

(#(R)  1)  (min(R)  x)2(min(R)  x)

• R の外部から複数の整数を借りてくると，s だけを σ(R)  min(R) + (#(R)  1)  x

借りてきた場合よりもコストが大きくなってしまう．

x が小さいほどこの値は小さくなるので，与えられた整数列中の最小値 s を使うことにすると，コストはσ(R)  min(R)  (#(R)  1)  s（2）これらのことから，実際のコンテストの場では，上のように求めるコストが最小であると信じて（あるいは祈って），プログラムを書いて提出することになるとなる．これと式 (1) を比較して，もし式 (2) の値ののであろう．そして，「正解！」と返事が返ってきて「こ方が小さければ，最小値 s を借りてきてソートし，それでよかったんだ」と喜ぶことになる．

うでなければ，輪の中だけで整数を入れ換えてソート

この Silly Sort の問題は，ここまでの考察が重要で，すればよさそうである．R が最初から最小値 s を含むプログラミングは比較的容易である．図 -3 に，問題場合は，式 (1) の値は必ず式 (2) より小さくなるので，を解く C 関数 sillysort の定義をあげる．この関輪の中だけでソートすればよさそうである．

数は，与えられた整数列 seq と，その長さ m を引数最後の例 4 には 〈8,7,2〉 と 〈4,5,3〉 の 2 つの輪がある．

として受け取り，整数列をソートするための最小コそれぞれについて，上のようにソートした場合のコスストを値として返す．関数本体は，初期化を行う部

トを計算してみよう．前者は最小値 s2 を含んでい分 (initialize) と，実際にコストを計算する部分るので，式 (1) からコストは 19 になる．後者に対して(compute) からなる．

は，式 (1) の値は 15，式 (2) の値は 23 となるので，小初期化部分では，まず整数列に対するグラフを配列

さい方の 15 を採用とする．合計 34 となり，これは最nodes に構築する．グラフのノード（節）は，構造体小とされるコストと一致する．

■プログラムtypedef struct {int value;
int place;} node;

前章の検討結果をまとめると，次のようになる．

で表現する．各 nodes[i](0  i  m) には，seq[i]（1）与えられた整数列にある輪を R1, R2,…, Rl とする．の 値 x を value フ ィ ー ル ド に 格 納 し，x の 最 終 位

また，整数列中の最小値を s とする．
（2）各 Ri に対して，式 (1) と式 (2) の値を計算し，その小さい方を cost(Ri) とする．

置（0 〜 m1 の い ず れ か の 値）を place フ ィ ー ルド に格 納し た ノ ー ド を 置 く． 各 整 数の 最 終位置を
求 め る た め に， 最 初 の for ル ー プ で temp と い う（3）cost(Ri) (i1,2,…,l) の和を求め，それを，与えら配 列 を 用 意 す る． 各 temp[i](0  i  m) に は， 整れた整数列をソートするための最小コストとして採数 seq[i] とその初期位置 i を設定しておいて，関用する．

数 sort_by_value を使って整数が昇順になるようにソートする（sort_by_value の定義は省略する）．

「最小コストである」と書かずに，「最小コストとしそして 2 つ目の for ループで，ソート済みの temp をて採用する」と書いたのは，このように求めたコスト使って nodes を初期化する．最後に，整数列の最小が最小であることを厳密に証明するのが難しいからで値を s に設定しておく．

ある．少なくとも，プログラミングコンテストの制限コストを計算するために，nodes を先頭から走査時間内には証明できそうにない．次のことは直観的にする．新しい輪 R（を構成するノード）に出会ったら，理解できるのであろう．

cost(R) を計算して cost に加える．コストの計算が620

45 巻 6 号

情報処理2004 年 6 月

int sillysort(int m, int seq[]） {int cost = 0, s, i;node nodes[1000], temp[1000];/* initialize */for (i = 0; i < m; i++） {temp[i].value = seq[i];temp[i].place = i;}sort_by_value(m, temp）;
for (i = 0; i < m; i++） {nodes[i].value = seq[i];nodes[temp[i].place].place = i;}s = temp[0].value;/* compute */for (i = 0; i < m; i++） {int j = nodes[i].place;if (j >= 0 && j != i） {int n = 1, amin, sum;amin = sum = nodes[i].value;
while (j != i） {int next = nodes[j].place;if (nodes[j].value < amin）
amin = nodes[j].value;sum += nodes[j].value;n++;nodes[j].place = -1;
j = next;}
cost += min(sum + (n-2）*amin,sum + amin + (n+1）*s）;}}
return cost;}

から順にたどって，sum (σ(R))，n (#(R))，amin(min(R)) を求める．そして，式 (1) と式 (2) の値を計算して，その小さい方，つまり cost(R) を cost に加える．
nodes の走査が終わると，与えられた数列をソートするための最小コストが cost に格納されているので，その値を返す．
図 -3 の定義では，グラフとの対応がつきやすいよ
うに，配列 nodes を初期化したが，nodes の代わりにソート済みの配列 temp を直接使ってそれぞれの輪のコストを求めてもよい．その場合，輪をたどる方向は，グラフの矢印と逆になるが，これは本質的でない．temp を直接使うことによって，次のメリットが生じる．
• 大きさ 1000 の整数配列 nodes を割り当てる必要がなくなる．
• nodes を初期化するための 2 つ目の for ループが不要になる．
• amin を更新するための if 文が不要になる．
ただし，図 -3 のプログラムは，メモリ使用量も実行時間もたいしたことはないので，頑張って最適化する必要はなさそうである．

■証明
整数列 A が与えられたときに，これをソートする
任意の手順 T に対して，そのコストが前章で最小コストとして採用した

図-3

Silly Sortを解くC関数��������( � �)以上であることを証明する．ここで，A に含まれる輪を R1, R2,…, Rl とする．
終わった輪に対しては，それを構成するノードを以以下の証明では，整数列中の位置が重要な役割を後の nodes の走査で無視したいので，place の値を果たす．そこで，整数列 A の位置のうち，Ri (i1,2,1（負の整数なら何でもよいが）にしておく．これに…,l) のノードに相当するもの全体（位置集合と呼ぶこ

よって，nodes[i] が新しい輪の一部であるかどうかとにする）を，Pi と表記することにする．図 -3 のプは，ログラムのように整数列を配列で表す場合は，Pi はnodes[i].place  0

インデックスの集合と考えればよいだろう．たとえばかどうかで判定できる．ただし，A が例 4 の整数列

nodes[i].place  i[8,4,5,3,2,7]の場合は，nodes[i].value は最初から最終位置にで，R1〈8,7,2〉，R2〈4,5,3〉 とするとき，位置集合は，あるのでスキップする．

P10,5,4，P21,2,3 となる．

cost(R) を計算するために，R のノードを nodes[i]手順 T によって，位置集合 P1, P2,…, Pl をいくつか

IPSJ Magazine Vol.45 No.6 June 2004621

�

�
�
�

図 -4

手順 T による位置集合のグループ分け（○は整数列中の位置，灰色の円は位置集合，破線の矢印は異なる位置集合間の整数の入れ換え，破線の円が最終グループ）

��

図 -5のグループに分ける．手順 T を適用して A をソートグループの合併と輪の本数（破線の円は，過渡的なグループ）する過程で，あるステップにおいて位置集合 P 内（のどこか）にあった整数と別の位置集合 P' 内にあった整数とを入れ換えたとき，P が属するグループと P'が属するグループを合併する．このように合併を繰り内の x と，グループ Y 内の y を入れ換えて，X と Y返して（合併するだけで分裂はしない），最終的に Aを合併したときを考える（図 -5 参照）．合併前は，xのソートが完了した時点のグループを，最終グループが属する輪（のすべての構成要素）は X 内にあり，yと呼ぶことにする（図 -4 参照）．輪 Ri を構成する整数が属する輪は Y 内にあるので，この 2 つは異なる輪

x は，最初は Pi 内にある．手順 T でソートする過程で，である．したがって，x と y を入れ換えることによっx は Pi と同じ最終グループに属する他の位置集合（のて G 内の輪の本数は１減少する．合併は全部で mどこか）へ移動した可能性はあるが，Pi が属さない最1 回起きるので，その回数だけ輪の数は減少する．一終グループへは移動していないはずである．また，T方，最初の輪の数は m 個であり，ソート完了時にはの各ステップで入れ換える 2 つの整数は，必ず同じ最終グループ内にある．

輪の数が����以下では，ある最終グループ G について考える．
簡単のために，G に属する位置集合を P1, P2,…, Pm とする．T のステップのうちで G 内の整数を入れ換えるものだけを考え，あたかも輪 R1, R2,…, Rm の全体をソートする手順であるかのように見なしたものをTG とする．TG のコスト，つまり R1, R2,…, Rm の全体をソートするコストの下限を，式 (1) のときと類似の方法で求めることにする．m1，つまり G がただ 1つの位置集合 P1 からなる場合，その最小コストが式�(��) 個になる．TG の１回のステップでは，輪の数は高々１しか増加しない（同じ輪の 2 つの整数を入れ換えたとき）ので，ステップ数 k は，�����( � �) �� ��( � ��) �������( � �) �� ��（3）以上である．
G は m1 回の合併によって作られたのだが，合併の際に入れ換えた整数の組を(x1, y1),(x2, y2),…,(xm1, ym1)(1) で与えられることは「試行錯誤」の議論で明らかなとしよう．これら 2(m1) 個の整数の中には，各 Riので，以下では m  2 と仮定する．

(i1,2,…, m) の要素が少なくとも 1 つ含まれている．

まず，TG のステップ数 k の下限を求める．グルー

位置集合 Pi 1 つだけからなるグループが他と合併す

プ G は，最初は m 個のグループ（それぞれの Pi がる際に，Pi から入れ換えによって出て行く整数は，1 つのグループ）だったものが，次々と合併していっ

必ず Ri の要素だからである．そのような整数を ai とて 1 つのグループになったのであった．グループ X

すると，(m1) 回の合併に要したコストは，

622

45 巻 6 号

情報処理2004 年 6 月

����� ������

（4）�����と表せる．ここで，各 bi (i1, 2,…, m2) は，R1, R2,…, Rm のいずれかの要素である．bi は，a1, a2,…, am�����のいずれかと一致するかもしれないし，それら以外かもしれない．b1, b2,…, bm2 のうちで，a1, a2,…, am の�

式 (�)� 式 (�)� 式 (�)�

�

�
���

いずれとも一致しないものを c1, c2,…, cu (0  u m���������������������� (��)�����

��(� (��)����(��)� (�(��)��)���)����

2) とする．a1, a2,…, am, c1, c2,…, cu のそれぞれは，合となる．ここで a0 は，G 内の最小の整数である．一併によって，最初にあった位置集合とは異なる位置集

般性を失うことなく，a0 が R1 の構成要素であったと合に移動する．だから，ソートが完了する前に，もとすると，min(R1)a0 だから，上の最後の式はの位置集合に戻らなければならない．戻るためのコスσ(R1)  (#(R1) 2)  min(R1)

トは，少なくとも� σ(R2)  min(R2)  (#(R2) 1)  a0�� ������

（5）�����…
 σ(Rm)  min(Rm) + (#(Rm) 1)  a0（7）である．R1, R2,…, Rm を構成する整数のうち，a1, a2,…, am, c1, c2,…, cu 以外のものは，最終位置へ移動するために少なくとも１回は移動する（最初から最終位置にあった整数は，それ 1 つでいずれかの輪 Ri を構成していたはずなので，a1, a2,…, am のいずれかと一致する）．それらのコストの総和は�

�(��)��

�����������

����( � �)

（8）以上である．このことは，すべての最終グループ G（位置集合 1 つだけからなるグループでも）に対して成り�� ���となる．これが TG のコストの下限であり，これは（6）�����

立つので，T の総コストも，前章で採用した最小コスト以上になることがいえる．となる．

上の証明では，与えられた数列 A の位置集合を手

ここまでのコスト計算には，合計(�����)�(���)�
���������

順 T がどのようにグループ分けするかに焦点をあてて，グループごとにソートに要するコストの下限（式� (��)����

� (��)��(���)(7)）を求め，それらの合計が，前章で採用した最小コスト以上になることを示した．手順が異なれば，一般にグループ分けも異なる．グループ分けが異なれば，下限の合計も異なる．その合計が，与えられた数列個の整数移動がカウントされている．TG のステップ

A をソートするための最小コストとなるグループ分け

数を k としたので，合計 2k 個の整数移動が起きていは，次のものである．A に含まれるそれぞれの輪 R にるはずである．その差を v とすると，対して，R が A の最小値 s を含まず，かつ式 (1) の値������
���

が式 (2) よりも小さい場合は，R（の位置集合）だけで� (��)��(���)であり，k を式 (3) で置き換えると，�������� (��)��

1 つのグループ（最終グループ）とする．そして，その他の輪（の位置集合）すべてを 1 つのグループとする．この最後のグループについては，式 (7) におけるa0 は s と一致するので，式 (7) の値は式 (8) と一致する．
（平成 16 年 5 月 10 日受付）となる．移動がまだカウントされていない整数を d1,d2,…, dv とすると，TG のコストは，IPSJ Magazine Vol.45 No.6 June 2004623