ああ、目覚めの珈琲は美味しい。 湿度はかなり低いが、相変わらず日射しは厳しく、暑い。 夕方帰宅。 お風呂に入ってから夕食の支度。 御飯を炊いてだしをひき、 鰤の照り焼き、高野豆腐と若芽の卵とじ、小松菜のおひたし、もろきゅう、 油揚げと葱のお味噌汁。 一汁三菜のつもりだったのだが、手を止めないようにしていたら一品多く作ってしまった。 今日もまた、小麦粉を塗るための刷毛が欲しいな、と思ったのだが、 常に「またこんど」になる。
でたらめに並んだものを正しい順番に並び換える、という事務仕事はしょっちゅうある。 言わゆる「ソート問題」だが、これには「クイックソート」と呼ばれる素晴しいアルゴリズムがある。 これを知っていると日常でもけっこう役立つ。 沢山の伝票を何かの順番に並び換えたいとしよう。 まず適当に一つ伝票を選ぶ。そしてこれよりも「大きい」伝票たち、 「小さい」伝票たちに分ける。 日常では大抵、これだけで手頃なサイズの二グループに分けられるので、 それぞれ自分流に並び換えて重ねればＯＫ。 伝票の数がもっと多い場合には、各グループ内で再度同じことをすればよい。 この手続きを最後まで繰り返すことが、 アルゴリズムとしてのクイックソート、ということになる。
一方で、全体を並び換える必要はなくて、 並び換えたあとの何番目かだけを知りたい、ということも良くある。 簡単なのは最大値と最小値だが、この場合は考えるまでもない。 しかし、丁度真ん中だけを知りたいとか、 上からベスト3の三つだけを知りたい、という問題は自明でない。 これについても「クイックソート」の応用で、「クイックセレクション」と呼ばれる名案がある。 例えば、上から 5 番目だけを知りたい、としよう。 まず、適当に一つを選ぶ。 そしてそれより大きいものと小さいものにグループ分けする。 大きい方のグループに5つ以上要素が含まれていれば、この中に答がある。 小さい方は調べなくてよい。 大きい方のグループに4つ以下しかなければ、逆に小さい方のグループに答がある。 例えば三つしかなければ、小さい方のグループの 5-3=2 番目を探せばよくて、 大きい方は調べなくてよい。 これを繰り返せば、すぐに答に辿り着く。 ベスト３だけを知りたいという問題も同じようにできる。 こちらは「部分ソート」と言ったりする。
プログラミングをしていると、ソートについては大抵ライブラリにあるので、 自分で実装する必要はないし、実装しようとしてはいけない。 しかし、セレクションはライブラリにないことが多い。 すると、賢い人は上のアイデアを知っているので(あるいは自分で思いついて)、 自ら実装しようとしてしまう。 でも、これはよろしくない。 このアルゴリズムを完全に正しく、かつ効率良く実装するのは、腕利きにとっても想像以上に難しい。 自分で書くと大抵バグ入りで、かつ、それほど速くないのだ。 一方でライブラリの中のソートや最大最小値関数は、 枯れ切っている上に超高速実装されている。 だから、本当の本当にその必要がない限りは、 これらを使ってダサい次善策をとるのが筋だろう。 こういう見極めが状況に応じてできるのが、プロというものである。
