コンパクトなプログラムvs.直感でわかるプログラム

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

バブルソートと比べてみよう

 2ページ目で作った「mysort1()」と第2回目で紹介したバブルソートを比べてみましょう。今回は「一番小さなものを順に取り出して、取り出した順に並べた」だけでした。

 さて、最初のバブルソートをもう一度考えてみましょう。隣り合ったものを比較して、小さいものがあればそれを左側に置く、という作業を繰り返しました。それを何度も繰り返すのですが、一度右端からはじめて左へ見ていった結果、何が行われるのでしょう?

 はじめのバブルソートプログラムにちょっと手を加えてデバッグ文をいれて、ループごとに元の配列がどのように変わるかを見てみました。

本質的には同じこと!

 最初のループの結果、左端には一番小さなもの(1)が出てきます。

 再度、右側から見ていきますが、その結果、その次に小さなもの(2)が出てきます。何度か繰り返しをしますが、一度右から左へ走査(スキャンといいますが)をするのは、その中で一番小さなものを見つけることをしていたのです!

 上で作ったmysort1()も、本質的にはバブルソートをしているのです!

 bubble_sort()とmysort1()とを見比べてどうでしょうか?いかにもbubble_sort()はコンパクトです。一見、何をしているかわかりませんが、効率良く動きそうです。それに比べてmysort1()は行数も多いです。しかし、直感的にわかりやすくはないでしょうか?

 プログラムには技巧的なところがあります。最終的には一見して何をしているかわからないプログラムになることもあります。けれど、設計する際は、自然に直感的にわかるところからはじめたいものです。

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

Think ITメルマガ会員登録受付中

Think ITでは、技術情報が詰まったメールマガジン「Think IT Weekly」の配信サービスを提供しています。メルマガ会員登録を済ませれば、メルマガだけでなく、さまざまな限定特典を入手できるようになります。

Think ITメルマガ会員のサービス内容を見る

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