考え方をひっくり返してみよう

プログラムではどう書く？

　この手順をそのままプログラムにしてみると、図2のようになるでしょう。

　プログラムの意味はわかると思います。上で書いた手順を「そのまま」プログラムにしたつもりです。

　whileループで配列から順に取り出します。ここではarray_pop()を使っていますがほかにも手があるかもしれません。そして、whileループの中にinsert_card()という関数がありますが、これが少しばかり「苦労する」関数です。

（1）1枚取り出す。
（2）適切な場所に挿入する。

　ここでも、（2）の詳細はあとで考えることにします。以前にも書きましたが、その中身については先送りします。今は、トップダウンで見たプログラムの構造に集中しましょう。

「安定」であるアルゴリズムとは？

　さて、このプログラムを前回のものと見比べてみましょう。前回示したものと同じものを図2に示します。

　とても似ていますね。

　前回は、取り出す時に工夫しました（pickup_small()）が、今回は並べる時に（insert_card()）工夫するわけです。

　あとは、insert_card()を考えればよいことになりました。

　繰り返しますが、プログラム全体の構造を先に決めます。その上で「こんな機能があったらいいのに」と想像します。ここでは「適切な入れ場所を決める関数があるといいなぁ」というわけです。あとはその機能を作るだけ。

　ところで、ここでちょっと豆知識を。これまで、ものの大小を比較することをしてきましたが、もし2つの数値が同じだったらどうなるのでしょう？

　普通は同じ大きさのものは「はじめに並んでいた順序のままに」します。このように同じ大きさのものが出現する順番が元と同じになる場合、そのソートアルゴリズムは「安定」であると言います。

　実は、アルゴリズムによっては「この順序が元のままになるとは限らない」のです。
つまり「安定」でないアルゴリズムがあるのです。

　この「安定」かどうかというのは、一見すると、同じ数値のものの並びが変わるだけでさほど重要でないと思われますが、実はとても重要です。

　みなさんがどこかの行列に並んでいて、なんらかの優先順位で並び替えをさせられたとします（飛行機の空席待ちをしているようなところを想像してください）。優先度が高い人が前に行くわけですからそれはあきらめますが、自分より後ろにいた同じ優先順位の人が、自分よりも前に行ったら腹が立ちますよね？ですから、こういう時の並べ替えは「安定」なアルゴリズムを使わないとまずいわけです。