この頃blogの記事でしめじソートが引っかかっているのが目についています。
どうもピタゴラスイッチで放送されるなどのタイミングで調べに来ているのでは？と推測しています。
で、それの大本のソート法をWikipediaで見てみたのですが、さすがに百科事典形式なので説明が難しいので初心者でもわかりやすくを目指してみます。
アルゴリズムとしては「マージソート」という名前で呼ばれている
「ソート」は並び替える動作、の意味なのは何となくわかると思います。
で、「マージ」の意味ですが、英和辞書では「併合する」「合併する」という意味で紹介されています。
簡単に言うなら「(いくつかに)分かれている同じ種類のものをくっつける」という動作です。
基本的にくっつける動作を主体にやっていきます。一応しめじソート風に説明します。(比較手順が逆になっていたりしますが、動き自体は同じです)
基本的な手順
基本的な手順を繰り返すことで全体を並び替える、という動作なのでその基本部分を紹介します。
中学生レベルで理解できるように組み立てていきます。今回は数字の並び替えです。
- まず、二つの並び替えが完了しているデータを用意する。それぞれをA1,A2とする。そして出力先をBとする。
A1:(0 1 5) A2:(2 3 7) B:()
- 繰り返しの起点[L1]
- A1の最後とA2の最後に注目する。
A1:(0 1|5|) A2:(2 3|7|) B:()
- A1の最後は[5](1回目)、A2の最後は[7](1回目)なので7の方が大きい。そのためA2から7を取り出してBの最初に移動する
A1:(0 1 5) A2:(2 3) B:(|7|)
- 繰り返し[L1]の終点。ここで繰り返し[L1]に戻る(戻ったことにして次の動作に注意)
- A1の最後とA2の最後に注目する。
A1:(0 1|5|) A2:(2|3|) B:(7)
- A1の最後は[5](2回目)、A2の最後は[3](2回目)なので5の方が大きい。そのためA1から5を取り出してBの最初に移動する
A1:(0 1) A2:(2 3) B:(|5|7)
- 繰り返し[L1]に戻る(2回目)
- A1の最後とA2の最後に注目する。
A1:(0|1|) A2:(2|3|) B:(5 7)
- A1の最後は[1](3回目)、A2の最後は[3](3回目)なので3の方が大きい。そのためA2から3を取り出してBの最初に移動する
A1:(0 1) A2:(2) B:(|3|5 7)
- 繰り返し[L1]に戻る(3回目)
- A1の最後とA2の最後に注目する。
A1:(0|1|) A2:(|2|) B:(3 5 7)
- A1の最後は[1](4回目)、A2の最後は[2](4回目)なので2の方が大きい。そのためA2から2を取り出してBの最初に移動する
A1:(0 1) A2:() B:(|2|3 5 7)
- 繰り返し[L1]に戻る(4回目)
- A1の最後とA2の最後に注目する。
A1:(0|1|) A2:(||) B:(2 3 5 7)
- A2にデータはないのでA1から[1]を取り出してBの最初に移動する
A1:(0) A2:() B:(|1|2 3 5 7)
- 繰り返し[L1]に戻る(5回目)
- A1の最後とA2の最後に注目する。
A1:(|0|) A2:(||) B:(1 2 3 5 7)
- A2にデータはないのでA1から[0]を取り出してBの最初に移動する
A1:() A2:() B:(|0|1 2 3 5 7)
- A1とA2の両方からデータが無くなったのでBが並び替えられたデータとなる。(並び替えられていることを例で確認)
A1:() A2:() B:(0 1 2 3 5 7)
というわけでアルゴリズムを実際の例を使ってやってみました。言葉で説明しているので見づらいですね・・・。
繰り返しの終了条件は「両方からデータが無くなったとき」となります。まあ、「片方のデータが無くなったときに残っているデータを追加していって」でもいいのですが、原理なので。
映像(というかアニメーション)がいかにに有利かどうかがわかります。gifのアニメーションでも作れば良かったですかね。
あと、通常は先頭方向からやるのですが、しめじソートの場合、終端方向からやっているのでこういう動きになります。
マージソートの名の由来どおり、A1とA2のデータをBへとくっつけながら並び替えている、という動きがわかると思います。
これを複数のデータがある場合に拡大して適応する
基本動作は「並び替え済みの2つのデータ列を別の場所へとくっつけながら並び替える」です。これをしめじソートとして成立させます。
- 並び替えが行われていないデータ列Aとデータ列Aをすべて記憶できるだけの大きさがあるデータ列Bを用意する。
(しめじソートではデータ列Aが机の下側に並んでいるしめじ。データ列Bが机の上側になる)
なお、以降の記述ではA1はAの1番目、という意味。A34はAの3番目、4番目を連続して見る、という意味とする。B:( ) A:( 5 7 0 8 3 1 6 4 2 )
- データ列Aとデータ列Bに1つずつ区切りを入れていく。
B:(| | | | | | | | | |) A:(|5|7|0|8|3|1|6|4|2|)- 繰り返しの起点[L2]
- Bに作成した区切りのうち最初と最後を除く偶数番目の区切りを消す。(2番目:5と7、4番目:0と8、6番目:3と1、8番目は6と4、10番目は最後なので無視)
- 分割した各領域に上で紹介した基本動作を当てはめる。例として|5|7|=>| |を動作させてみる。
- A1の最後は[5]、A2の最後は[7]なので7の方が大きい。そのためA2から7をとりだしてB12の最初に移動する。
- A2にデータはないのでA1から[5]を取り出してB12の最初に移動する。
- A1とA2の両方からデータが無くなったのでB12が並び替えられたデータとなる。そのほかも同様にやってみる。くっつけた部分の区切りは消す。
- AとBを入れ替える。(プログラムなどで実際に入れ替えるのが難しいときは名前を交換するといった動作をとる)
- 繰り返し[L2]の終点。ここで繰り返し[L2]に戻る(戻ったことにして次の動作に注意)
- Bに作成した区切りのうち最初と最後を除く偶数番目の区切りを消す。(2番目:7と0、4番目:8と1、6番目:3と4、8番目は最後なので無視)
- 分割した各領域に基本動作を当てはめる。例として|5 7|0 8|=>| |を動作させてみる。
- A12の最後は[7]、A34の最後は[8]なので8の方が大きい。そのためA34から8をとりだしてB1234の最初に移動する。
- A12の最後は[7]、A34の最後は[0]なので7の方が大きい。そのためA12から7をとりだしてB1234の最初に移動する。
- A12の最後は[5]、A34の最後は[0]なので5の方が大きい。そのためA12から5をとりだしてB1234の最初に移動する。
- A12にデータはないのでA34から[0]を取り出してB1234の最初に移動する。
- A12とA34の両方からデータが無くなったのでB1234が並び替えられたデータとなる。そのほかも同様にやってみる。くっつけた部分の区切りは消す。
- AとBを入れ替える。
- 繰り返し[L2]に戻る(2回目)
- Bに作成した区切りのうち最初と最後を除く偶数番目の区切りを消す。
- 分割した各領域に基本動作を当てはめる。くっつけた部分の区切りは消す。
- AとBを入れ替える。
- 繰り返し[L2]に戻る(3回目)
- Bに作成した区切りのうち最初と最後を除く偶数番目の区切りを消す。
- 分割した各領域に基本動作を当てはめる。くっつけた部分の区切りは消す。
- 区切りが最初と最後のみとなったためこれでBが並び替えが完了している状態となる
手順を追っていきました。長いですがこんな感じになります。
繰り返しの終了条件は「すべてのデータがくっついたこと」になります。
このマージソート(しめじソート)の肝は「小さい部分から少しずつ並び替えを行って部分を拡大していく」ことにあります。
ピタゴラスイッチでもう一つ出されていたじゃがいもソート(クイックソート)は「大きい部分を分割しながら小さくしていく」という動作で反対になっているわけですね。
一応アルゴリズムらしく利点と欠点を
これを言っておかないとプログラマらしくはないですね。
利点
- 最悪の場合でも計算量は
となるため速度が安定する - データ列は常にどちらか一方向からしか調べない(今回のマージソートでは後方からやれば順に処理ができる)ため順次処理しかできないデバイスでも処理ができる。
- 比較上は同じデータ(人名で名字だけを並び替えている場合など)が現れたとしてもそのときの手順を決めておけば順番が逆になることはない
欠点
- 必ずデータ列と同じデータが記憶できる作業領域が必要となる。(添え字番号だけの並び替えであってもその添え字分の領域が必要)
- データが乱数列に近くなると速度はクイックソートなど別の方法に対して不利になる
ほかの部分についてはさすがにWikipediaなどを参考にしてください。
もう一つの方も解説しようかな・・・
blogを移転させている影響でアクセスが大幅に下がっています。当たり前ですが。
ちょっと箔をつけたいのでいろいろと記事を増やしていこうと思っています。そのタイミングでもう片方の解説というのもありだな～と思っています。
2014/05/25 追記(というより修正)
併合させるBについて、記述が「最後」になっていましたが「最初」が正しいです。見事に逆でしたね・・・。