2007年11月07日
ハロプロ・ソートの解説
ハロプロ・ソートで遊んでいただきありがとうございます。
様々なブログで取り上げていただいており、それを検索して読むのは楽しいのですが、
中にはこのハロプロ・ソートが占いの類であると誤解されている方もいるようです。
そこで、このページではソートの原理について簡単に解説してみようと思います。
理系科目が好きな中高生が理解できるレベルの話にしようと心がけていますが、
部分的に難しい話になってしまうかもしれません。その辺はご了承ください。
▼ ソートとは？
ソート（sort）とは、データの集まりをある順番に従って並べることです。
例えば「4,6,2,9,1」という数字を小さい順に「1,2,4,6,9」と並べ替えるのがソートです。
ハロプロ・ソートはメンバーの集合を好きな順・推し順に並べ替えるというソートです。
▼ 単純なソート方法
上の例で「4,6,2,9,1」という数字の集まりが与えられたときに、
多くの人は最初に5つの数字を眺めて「あ、1が一番小さいな」と考えます。
次に1を除いた4つの数字の中で最も小さい数字である2を見つけます。
さらに1、2以外の3つの数字から最も小さい数字・・・、と繰り返していって
最終的に 「1,2,4,6,9」 という整列された数字の集まりを得ます。
これは最も簡単なソート方法ですが、実は効率の良い方法であるとは言えません。
数字が5つ程度と少なければ一番小さい数字を一瞬で見つけることができますが、
50個の数字の中から小さい順に1つずつ数字を選び出すのはとても面倒です。
それでも大小関係が厳密な数字ならまだ良い方で、50人のハロプロメンバーの中から
好きな順に1人ずつ正確に選び出していくのには非常に長い時間が必要です。
▼ ソートアルゴリズム
問題を解決するための手順のことをアルゴリズム（algorithm）と呼びます。
世の中にはソートのためのアルゴリズムを専門的に研究する研究者がいて、
効率の良いソートアルゴリズムが実際にいくつも考案されています。
具体的などんなアルゴリズムがあるのかはwikipediaを参照してください。
ハロプロ・ソートではマージソート(mergesort)というアルゴリズムを使っています。
ソートアルゴリズムの多くは（マージソートを含め）一対一の比較を繰り返して
最終的に全体が整列されるという方法を採っています。たくさん候補の中から
一番のものを選ぶのは難しくても、2つの中で優劣を決めるのは比較的簡単な
場合があります。これもソートアルゴリズムを利用するメリットであると言えます。
▼ マージソートの手順
ハロプロ・ソートで採用しているマージソートの一般的な手順を説明します。
1. データ列（データの集合）を半分ずつ2つに分割する。
2. 分割されたそれぞれのデータ列をソートする。
3. ソートされた2つのデータ列をマージする。
手順2.ではマージソートを繰り返して適用します。
分割されたデータ列に含まれる個数が2以下になるまで分割を繰り返し、
できあがったデータ列を次々とマージ（合併）していくことになります。
▼ マージソートの動作例
例として
川*’ー’） ||ｃ| ・e・)| 从*＾ｰ＾） 从*･ ｡.･） 从*´ ヮ｀）
というデータ列をソートしてみます。ここではソートの仕組みを確かめるため
好きな順ではなく苗字の五十音順にソートすると決めておきます。
まず、データを2分割します。
┌ 川*’ー’） ||ｃ| ・e・)| 从*＾ｰ＾） ┤ └ 从*･ ｡.･） 从*´ ヮ｀）
上のデータは3個あるので、さらに分割します。
┌ 川*’ー’） ||ｃ| ・e・)| ┌─┤ ｜ └ 从*＾ｰ＾） ┤ └ 从*･ ｡.･） 从*´ ヮ｀）
それぞれのデータ列を苗字の五十音順で並べ替えます。
（一番下のデータ列の順序が入れ替わります。）
┌ 川*’ー’） ||ｃ| ・e・)| ┌─┤ │ └ 从*＾ｰ＾） ┤ └ 从*´ ヮ｀） 从*･ ｡.･）
続いてデータ列をマージします。まずはこの部分から。
┌ 川*’ー’） ||ｃ| ・e・)| ┤ └ 从*＾ｰ＾）
データ列の先頭を比較し、五十音順で早い方を合併後のデータ列に移します。
┌ 川*’ー’） ||ｃ| ・e・)| 从*＾ｰ＾） ← ┤ └ （空）
片方のデータ列が空になったら、残った方を新しいデータ列の後ろに繋げます。
┌ （空） 从*＾ｰ＾） 川*’ー’） ||ｃ| ・e・)| ← ┤ └ （空）
全体では下のような感じになりました。次はこれをマージします。
┌ 从*＾ｰ＾） 川*’ー’） ||ｃ| ・e・)| ┤ └ 从*´ ヮ｀） 从*･ ｡.･）
まずは両データ列の先頭を比較して・・・
┌ 川*’ー’） ||ｃ| ・e・)| 从*＾ｰ＾） ← ┤ └ 从*´ ヮ｀） 从*･ ｡.･）
こうなります。このあと先頭同士の比較を繰り返します。
┌ ||ｃ| ・e・)| 从*＾ｰ＾） 川*’ー’） ← ┤ └ 从*´ ヮ｀） 从*･ ｡.･） ↓ ┌ ||ｃ| ・e・)| 从*＾ｰ＾） 川*’ー’） 从*´ ヮ｀） ← ┤ └ 从*･ ｡.･） ↓ ┌ （空） 从*＾ｰ＾） 川*’ー’） 从*´ ヮ｀） ||ｃ| ・e・)| ← ┤ └ 从*･ ｡.･）
片方のデータ列が空になったので、残った方を付け加えます。
┌ （空） 从*＾ｰ＾） 川*’ー’） 从*´ ヮ｀） ||ｃ| ・e・)| 从*･ ｡.･） ← ┤ └ （空）
これでソート完了です。当初の目的通り五十音順に並べ替えられました。
▼ 引き分けの処理
一般的なマージソートのアルゴリズムは上に述べた通りですが、
ハロプロ・ソートでは「引き分け」「どうでもいい」という選択肢を追加しています。
ネタバレになりますが、これら二つの処理の中身は全く同じです。
どちらの場合も優劣を付けられなければ数学的に違いはないので。
引き分けの処理ですが、「ＡとＢは同価値である」という情報を保存しておいて
マージする際に合併後のデータ列に同時に移す（下図参照）ことにしています。
これによって通常のマージソートよりも比較回数を少なくしています。
（比較画面に表示されるものを赤で表示） ┌Ａ ┌─┤ │ └Ｂ ┤ │ ┌Ｃ └─┤ └Ｄ ↓（引き分けを選択） ┌Ａ＝Ｂ │ ┤ │ ┌Ｃ └─┤ └Ｄ ↓（Ｃを選択） ┌Ａ＝Ｂ ┤ └Ｃ，Ｄ ↓（Ｃを選択） ┌Ａ＝Ｂ Ｃ ┤ └Ｄ ↓（Ａを選択） Ｃ，Ａ＝Ｂ，Ｄ
▼ 最後に・・・
簡単に説明しようと思っていたのですが、この手の解説に慣れていない方にとっては
難しい話になってしまったかもしれません。私が説明に慣れていないというのもありますが・・・。
質問・ツッコミなどは掲示板に書いていただければ対処します。
なお、ハロプロ・ソートのソースコードは（非常に汚いですが）再利用してもらって構いません。
（※丸ごとコピペするとinfoseekが自動挿入する広告コードが残るので注意してください。）
報告などは必須ではありませんが、教えていただけたら遊びに行きます。
【追記】
ソースコード編集用のファイルを用意しました（こちら）。解凍して使ってください。
メンバーの名前を変更する（ファイル10行目以降のコメント参照）だけで流用可能です。
【さらに追記（08/12/15）】
テスト用コードはこちら。まだ途中です。。。
【またもや追記（09/02/03）】
需要があるかもしれないので、以前のバージョンも置いておきます。こちら。