PR

直感的にわかるソートの方法は?

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

PHPでプログラムを書いてみよう

 「第1回:アルゴリズムからプログラムを学ぼう!(http://www.thinkit.co.jp/article/62/1/2.html)」では、バブルソートの原理を説明しましたが、今回はまずこれをプログラムにしてみましょう。

 前回のおさらいですが、バブルソートの考え方は次のようなものです。カードが横一列に並んでいるものとします。

 (1)右端から始めて、それとすぐ右隣とを比較する。

 具体的には右側が左側よりも小さければ入れ替えます。それ以外のときはそのままにしておきます。視点を1つ左に移します。

 (2)(1)を繰り返す。

 ではこれをPHPで書いてみます。

プログラムの内容

 (1)バブルソートの関数ですが、引数として受け取った配列の中を並べ変えるものとします。

 (2)カードの枚数が「$size」に入ります。

 (3)ここで、右端から左に向かって比較しますが、どこまで見るかを示す、いわば限界が「$last」です。最初は左端まで見ますが、次はその1つ右側まで、というように比較する範囲を狭めます。そのためのループです(無駄ですが、毎回左端まで見ても構いません)。

 (4)比較する右端のインデックスは、見る対象枚数よりも1だけ少ないので「$size-1」が比較対象の最初の位置を示しています。

 (5)ここで実際の「比較」を行います。左側が右側より大きければ...

 (6)入れ替えを行います。この入れ替えにはわざわざ「swap」という関数を作ってそれを使っています。もちろん、ここに入れ替えるコードを書いても構いませんが、入れ替える対象物によっては、手順が長くなるかもしれません。そのような場合も想定して、独立した機能にします。そのために関数にするわけです。

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

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

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

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

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