PR

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

2008年5月23日(金)
須藤 克彦

プログラムの基礎を整理しよう

 バブルソートのアルゴリズムからプログラムを考える本連載ですが、「第3回:コンパクトなプログラムvs.直感でわかるプログラム(http://www.thinkit.co.jp/article/62/3/)」では、一見異なるアプローチながらバブルソートと同じような方法でプログラムを書きました。今回はまた少し違うアプローチをしてみましょう。

 同じことをするのにいくつも方法を考えるのは、まわりくどいと思われるかもしれませんが、プログラムの基礎になる考え方を整理する、つまり設計をすることであり、とても重要です。そして、プログラムはそれを「そのまま」表現したものであるべきです。

 前回は、カードの集まりの中から1枚を「取り出す時に」一番小さいものを選び、あとはそれを「並べるだけ」でソートを実現しました。

 これとは逆の考え方ですが、次のような方法が考えられます。

(1)カードの集まりからどれでもよいので1枚取り出す。
(2)別のところに順に並べる時に「適切な」位置に入れる。つまり、選んだカードよりも大きいものがあればその「前」に置く。
(3)(1)(2)を元のカードの集まりがなくなるまで繰り返す。

どうやって適切な置き場所を探すか

 取り出す時は楽をしますが、並べる(置く)時に少しばかり知恵を使います。

 上の(2)で「適切な」置き場所を探しますが、その方法は次のような手順になるでしょ
う。

 上の図の右側にあるカードはソートされたものですから、小さい順に並んでいるはずです。ですから、取り出したカードを、ソートされたカードの左端から順に比べていきます。

 取り出したカードよりも大きなカードに出くわしたら、その前が「適切な」場所であることがわかります。

 例えば、右側のカードが以下のように並んでいるとします。

  2、3、6、8

 この時取り出した1枚が5だったとすれば、左から順に見ていって6が現れたところに5を「挿入」することになります。よって並びは以下のようになります。

  2、3、5、6、8

神戸情報大学院大学
1980年立命館大学理工学部卒、独立系ソフトハウスに入社。CやFORTRANコンパイラなどの言語処理系の設計・開発に約10年間従事。その後ユーザ系企業でUNIXによるクライアントサーバシステムの設計・開発を主導。同時に企業の内外で人材育成に注力する。現在は神戸情報大学院大学で講師として教鞭(きょうべん)をとる。「ソフトウエア工学の基礎を勉強してオールラウンドプレーヤーを目指せ」が技術者育成についての口癖。http://www.kic.ac.jp/professors/sudo/index.html

Think IT会員サービス無料登録受付中

Think ITでは、より付加価値の高いコンテンツを会員サービスとして提供しています。会員登録を済ませてThink ITのWebサイトにログインすることでさまざまな限定特典を入手できるようになります。

Think IT会員サービスの概要とメリットをチェック

他にもこの記事が読まれています