>>Delta

何たらソートシリーズの解説「マージソート」

2008年6月16日

何たらソートシリーズの解説「マージソート」

最近流行りの何たらソート。東方ならなんとかわかるので東方キャラソートやってみました。結果はともかく、マージソートを実際にクリックしながら学べるのは楽しいですね。

以下マージソートという方法をご存知ない方向けの簡単マージソート解説。

マージソートとは

  • 【図1: マージソート(1)】

図のように既にソートされた(小さい順に並んでいる)2つの数列の頭から1個ずつを取り出して比較し、小さい方から順に新しい数列に詰めていくという方法を使って、2つのソート済み数列を1つの大きなソート済み数列に統合していく方法です。

最初は

  • 【図2: マージソート(2)】

このように要素が1個だけの数列から始めて、出来上がった要素が2つの数列どうしでさらにマージソート、というように繰り返して徐々に数列を長くしていきます。

  • 【図3: マージソート(3)】

繰り返すとトーナメントを勝ち上がるように徐々に要素同士の大小関係が確定していきます。

従って、2つの数列から1個ずつ取り出している間は、片方をクリックしたとき、その要素の次に並んでいた要素が自動的に前に出てきます。

  • 【図4: マージソート(4)】

要素の比較が終わって比較用の数列が空っぽになると、次の新しい数列の評価に移るので両方のボタンが同時に新しい要素に切り替わります。

  • 【図5: マージソート(5)】

ソートが進むにつれて数列は長くなるので、段々と片方だけ変わるパターンが多くなっていき、しかも既にある程度ソートされたもの同士を比較するので微妙な判断を迫られる頻度も徐々に増えていきます。

以上、マージソートについてのお話しでした。こんなことを考えながらクリックすると、徐々にソートが進んで数列が長くなっていく様子が実感できて楽しいです。

ちなみに、マージソートとは2つの数列を合体させる(マージする)うちにソートが完了するからそういう名前が付いているそうです。諸々の事情でライバルの“クイックソート”より採用は少ないですが、最速のソートアルゴリズムの一種です。

余談: ライバルのクイックソートはソートの前半で間違った大小を付けると、ソート結果に大きく響くので、人間が判定するような並び替えには向いてないんだと思います。

おまけ
順位 名前
1 八雲藍
2 四季映姫・ヤマザナドゥ
3 鈴仙・優曇華院・イナバ
4 射命丸文
5 犬走椛
6 稗田阿求
7 洩矢諏訪子
8 上白沢慧音
9 ミスティア・ローレライ

ソートした本人の感想としては、みすちーの順位高すぎでね?です。

投稿者 CASPAR003
投稿時刻 23:37
カテゴリー 雑記
コメント 0 件
トラックバック 0 件
記事へのリンク http://www.caspar003.info/delta/archive/2008/06/16/2337.html
コメント
投稿者
コメント
トラックバック
  • トラックバック

ブログ情報

カレンダー
2018年2月
1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28
最近のエントリー
最近のコメント
コメントを頂いたエントリー
コメントをくださった方一覧
コピー用紙の裏表
でった☆
CASPAR003
あのー
CASPAR003
amumo
CASPAR003
mariko
kazu
お仕事で青ざめた話
iun
iun
CASPAR003
AcrobatでPDFの一括印刷
Caesar
CASPAR003
Shadeのレンダラー仕様メモ
iun
CASPAR003
ブログ同盟本 C87 3日目 東S-04b
CON$
CASPAR003
Ca3 Post_Effector 2.0
sisioumaru
CASPAR003
sisioumaru
CASPAR003
Shade15について雑感
iun
CASPAR003
iun
色について
iun
CASPAR003
Lv67
iun
CASPAR003
雪まつり行ってきたよ
iun
CASPAR003