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

insert_card()を作ろう

　さて、先送りしていたinsert_card()を作りましょう（図3）。

　今、要素$eを配列$arrの「適切」な場所に「挿入」したいという状況です（図3の1）。

　適切な場所を決めるためには次のようにします。

　まず並びを順に見ていって、要素$eよりも小さいものがあるうちはさらに次を見ていき、それよりも大きなものが現れれば、その直前が目的の場所です。

　ですから、今入れたい要素よりも大きなものが現れれば（図3の2）ループを抜けます（図3の3）。その時の配列の位置（$i）が、目的の場所ということになります（図3の4）。

　なお、入れ先の配列が空の場合は、$iが0の状態で（つまりforループを一度も回らずに）ループを抜けますから、配列の先頭に要素を追加することになります。

比較作業を何回行っているか？

　さて、シンプルな（?）バブルソートからはじめて2つのバリエーションを示しました。いかがでしょうか？直感的には、はじめのものよりは、あとの2つの方がわかりやすかったのではないでしょうか。

　先のpickup_small()版も本質的にはバブルソートと同じことをしていましたが、今回の insert_card()版も実は同じことをしています（このあたりの分析は次回に説明します）。

　直感的なわかりやすさはともかく、それらの計算量（計算時間）について少しだけ考えてみます。どの方法でも、2つのモノの大きさを比較するわけですが、いずれも「総当たり」をしています（厳密には、純粋なバブルソートと今回の方法とでは若干違います）。
　何回の比較作業をしなければならないでしょう？

　n枚のカードがあったとして、1枚についてほかの（n-1）枚と比較するわけですから、全体ではn*（n-1）／2回の比較をすることになります（2枚の比較について、双方からの回数をカウントしているので2で割っています）。

　これを近似的にいえばn^2（nの2乗）の計算量です。ですから枚数が倍になると計算量は4倍になります。計算時間（処理時間）はほぼ計算量に比例しますから、枚数が10倍になると計算時間は100倍かかることになります！

　ものを並べ替えるという作業はコンピュータシステムの中では頻繁に発生します。それが、データ量の2乗に比例するというのは、遅すぎますね。

　そこで、次回（最終回）は、もっと性能のよいソートアルゴリズムを紹介するとともに、ソート以外の重要なアルゴリズムも紹介しましょう。