アルゴリズムで頭の体操第3回

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

直感的な方法をプログラミング　「第2回：直感的にわかるソートの方法は？（/article/62/2/index.html）」では、バブルソートの原理に従ったプログラミング方法を紹介しました。しかしこの方法は、理屈はわかるのですが、筆者には複雑すぎて直感的には理解しにくいものでした。それで別のアプロー

須藤克彦

2008年5月16日 20:00

直感的な方法をプログラミング

　「第2回：直感的にわかるソートの方法は？（/article/62/2/index.html）」では、バブルソートの原理に従ったプログラミング方法を紹介しました。しかしこの方法は、理屈はわかるのですが、筆者には複雑すぎて直感的には理解しにくいものでした。それで別のアプローチを考えました。

　（1）トランプ集まりの中から一番小さいものを取り出す。
　（2）それを別のところに順に並べる。
　（3）（1）（2）を（1）のトランプがなくなるまで繰り返す。

これを「そのまま」プログラムにしてみましょう。図1のような感じでしょうか。

プログラミングのポイントは？

　図1に示したプログラミングの重要なポイントは以下のような「ループの部分」です。

　　while( $e = pickup_small( &$arr ) ) {
　　array_push( $new_arr, $e );
　　}

　言葉で書けば次のようになります。

　（1）配列（$arr）から一番小さいものを取り出す。
　（2）取り出すものがなければおしまい。
　（3）取り出したものを新しい配列に付け加える。
　（4）（1）に戻って繰り返す。

　「1枚取り出す」ときに、もちろん1番数字の小さなものを取り出すのですが、それは取り出すときに考えましょう（細かいことは先に延ばすのがミソ！）。

　これで話は単純になりました。あとは一番小さいものを取り出す関数を作るだけです。