PR

 私の経験上、最近のIT企業の新人研修で人気があるプログラミング言語は、ダントツでJavaです。ただし、Javaの言語構文だけマスターしても、プログラムを作れるようになれません。アルゴリズムの考え方を学び、アルゴリズムをプログラムに置き換える練習が必要です。そんなわけで、アルゴリズムをJavaプログラムに置き換えることをテーマとしたセミナーの要望が多くあります。セミナーの一部をWeb上で再現させていただきます。

 ソート(整列)のアルゴリズムとして有名な「バブルソート(babble sort)」の手順をお教えしましょう。アルゴリズムは、丸暗記して覚えるものではありません。自分なりにアルゴリズムのイメージをつかむことが大事です。

 バブルソートのイメージをつかむ例として、こんなのはいかがでしょう。皆さんは、小学校の体育の先生になったとします。ゼッケンを付けた5人の生徒に「全員集合!」と声をかけたところ、バラバラに並んでしまいました。皆さんは、バブルソートのアルゴリズムを使って、前から後ろに向かってゼッケン番号の小さい順にソートします。

 アルゴリズムの手順を覚えるには、手作業でやってみることをお勧めします。2cm×2cmぐらいの小さな紙を5枚用意して、その上に1~5の数字を書いてください。この紙を生徒のゼッケン番号に見立てて、手作業でバブルソートをやってみましょう。

 まず、一番ゼッケン番号が小さい生徒を決定します。先生は、列の末尾(右端)に行き、その位置の生徒と1つ前の生徒のゼッケン番号を比べます。[1]と[3]ですから、後ろにある[1]の方が小さいですね。そこで、[1]と[3]の生徒を交換します。次に、先生は、一歩先に(左に)進み、その位置の生徒と1つ前の生徒のゼッケン番号を比べ、小さい方が前になるように交換します。これを繰り返せば、一番ゼッケン番号が小さい生徒が決定します。その生徒を体育座りで座らせます。紙を下げて、体育座りしたことにしましょう。

 今度は、2番目にゼッケン番号が小さい生徒を決定します。そのためには、残りの4人の生徒に対して、先ほどと同じ手順で比較と交換を行います。以下同様にして、3番目にゼッケン番号が小さい生徒、4番目にゼッケン番号が小さい生徒を決定して行けば、5人の生徒全員のソートが完了します(4番目の生徒が決定すれば、自動的に5番目の生徒が決定する)。これが、バブルソートの手順です。生徒が一人ずつ決定する様子が、まるで水の底から泡が浮き上がるようでしょう。だからバブル(babble=泡)ソートと呼ぶのです。

 さて、ここからがポイントです。バブルソートのアルゴリズムは、バッチリわかりましたね。それでは、このアルゴリズムをプログラムに置き換えてみましょう。どうしたらよいと思いますか?ちょっと悩んでしまいますね。ここでは、私が考案した「実況中継方式」という、とっておきの秘策を伝授しましょう。

 皆さんは、野球の実況中継を聞いたことがありますね。「7回裏、ジャイアンツの攻撃。ツーアウト、ランナーなし。バッターは、4番高橋であります。ボールカウントは、ツーストライク、スリーボール」「ピッチャー投げました!バッター打った!」という感じです。

 野球の実況中継は、現在の状況をいくつかの数値の変化で伝えます。1回~9回まで変化するイニング数、1番~9番まで変化する打順、1~3まで変化するストライクカウント、1~4まで変化するボールカウント、そして1~3まで変化するアウトカウントなどです。変化する数値の現在の値を言うことで状況を示せます。状況が示せたら、ピッチャー投げた、バッター打った、という処理が行われます。この「状況の変化」と「処理」というものが、アルゴリズムをプログラムに置き換える秘策となるのです!

 それでは、やってみましょう。受講者の皆さんは、隣同士でペアになってください。一方の人が、5枚の紙をバブルソートの手順で並べ替えます。その様子を、もう一方の人が実況中継してください。バブルソートにおける処理は、「比較しました」と「交換しました」です。それでは、状況の変化を示す数値は何でしょう?

 それは、「現在、何番目の生徒を決定しようとしているか」と「現在、先生はどの位置にいるか」です。恥ずかしがらずに、声を出して実況中継してみましょう。「現在、一番ゼッケンが小さい生徒を決定しようとしています。現在、先生は列の末尾にいます」と状況を言ってから、「隣同士の生徒を比較しました!」「後ろの方が小さいので交換しました!」という実況に合わせて紙を動かしてください。それでは、はじめてください!終わったら、実況中継をする人を交代してください。

 実況中継できれば、プログラムに置き換えられます。バブルソートでは、状況の変化を示す数値が2つ登場します。プログラムでは、それらが変数の変化となります。ここでは、「現在、何番目の生徒を決定しようとしているか」を変数n、「現在、先生はどの位置にいるか」を変数pで表すことにしましょう。nは、1~4まで変化します。pは、5~n+1まで変化します。生徒に相当するデータは、配列s[ ]で表します。Javaでは、配列の[ ] 内の番号(インデックス)が0から始まる数値となるので、nは0~3までの変化、pは4~n+1の変化となります。配列の要素、すなわち5人の生徒は、s[0]~s[4]となります。あらかじめs[0]~s[4]に、4、2、5、3、1という値(ゼッケン番号)が代入されているとします。

 nが0~3まで変化することは、for (n = 0; n < 4; n++) { } というfor文で表します。そのfor文の { } の中に、pが4~n+1まで変化することを表す for (p = 4; p > n; p--) { } という別のfor文が入ります。「for文の中にfor文があるのが苦手です!」なんて言わないでくださいね。たった2つの数値の変化ですよ。多くの数値が変化する野球の実況解説に比べたら、とっても簡単なものです。

 2つのfor文によって、状況の変化が表せました。後は、内側のfor文の { } の中に、「隣同士の生徒を比較しました!」「後ろの方が小さいので交換しました!」という処理を書けばよいのです。

 プログラムを作ってください。ちゃんとソートできましたね。それでは、最後に面白いことをやってみます。実際に、プログラムに実況中継してもらいましょう。そのためには、System.out.println( ) メソッドを使って、実況中継の言葉を画面に表示させます。どのような実況中継をするかは、皆さんにお任せします。一言実況中継するたびに、現在の配列の内容を表示するというのもいいでしょう。どうです。楽しいでしょう!