Charlie's Cocktail BAR

  • −お酒は責任のとれる範囲で飲みましょう−

[玄関] [履歴] [メニュー] [検索] [本棚] [カクテル講座] [はばかり] [はしご]

たった四人の卒園式も無事に終わり、四月に学校が始まるまでは上の娘も自宅待機と相成ったのですが、お弁当を食べてくれる人が減ったということはそれだけぼくが昼食を用意しなければならない口が増えたということで。自分ひとりならいくらでも横着できるんですけどね、やあ、今日のお昼は何にしようかしら(^^;)

ちょっとした興味があったのでソート(並べ替え)のアルゴリズムを調べていたのですが、シェイカー・ソートなる方法があるんですね。バブル・ソートのバリエーションですから特別速くて便利なルーチンってわけじゃないんですが、ここにシェイカーという名前がつくかとちょっとおもしろかったので簡単に紹介してみましょう。

一般にバブル・ソートと呼ばれるソートの場合、たとえば3412という数列を並べ替えるとすると、

(1)最初の3、4の並び順は問題なし。
(2)二番目の4と1の組は、並び順が違うので位置を入れ替える(3142)
(3)続いて三番目、(2)の手順で4と2になりましたが、これもやっぱり並び順が違うので位置を入れ替える(3124)
(4)四番目の組はなし。ここまでで4より大きな数はないはずだから、次回は4の前までチェックすればよい、と。
(5)最初に戻って、3と1の並び順をチェック。これも順番が違うので位置を入れ替える(1324)
(6)続いて二番目、3と2の組も並び順が違うので位置を入れ替える(1234)
(7)続いて三番目……は4の方が大きいのがすでに(4)でわかっているのでチェックする必要なし。今度は3の前までチェックすればよし。
(8)さらに最初に戻ると、今度は1と2の並び順が正しいので、これはそのまま。
(9)続いて二番目……は、チェックする必要がなし。ここまでで入れ替えた箇所はないからソート終了。

ってな具合になるのですが、このアルゴリズムの場合、たとえば2341という数列を並べ替えようとすると、(1)234までは問題なしだから、4と1を並べ替えて最初に戻る(2314)、(2)23までは問題なしだから、3と1を並べ替えて最初に戻る(2134)、(3)2と1を入れ替えて最初に戻る(1234)、(4)全部チェックしても並べ替えるべき箇所がないのでソート終了、と、三回最初に戻らないといけないのに対して、同じやり方でも後ろから、どちらが小さいかに注目してソートすると、入れ替える回数は同じなんですが、(1)4より1の方が小さいから4と1を入れ替え(2314)、(2)3と1を入れ替え(2134)、(3)2と1を入れ替え(1234)、(4)最後に戻って、チェックしても並べ替える場所がないのでソート終了、と、(最初/最後に)戻る回数が少なくてすみますよね。だから、先頭からチェックし終えたら、最初に戻るのではなく、今度は先頭に向かって戻るようにチェックしていけば、ソートの平均は速くなるのではないか――というのがシェイカー・ソート。

ま、実際に速くなるかどうかはプログラムを組むなり手計算してみるなりしていただきたいのですが……

この行ったり来たりの動作、最終的には真ん中あたりで止まるのですからほんとは振り子ソートとでも呼ぶべきだと思うのですが、これを最初に紹介した人はやっぱりカクテル好きの人だったのでしょうかね?(笑)

それにしても……こんな風の強い日に洗濯をしたぼくもぼくですが、物干し竿ごと洗濯物が飛んでいくってのはどういうことかと_no

#おまけ:上の説明では「ソートされていることがわかりきっている」箇所でチェックを巻き戻して/折り返していますが、それをしなければ、つまりソートされていようといまいととにかく端から端までチェックして回れば確かにシェイカー型と言ってよいかもしれません。確かに時間の無駄なんですが、使い捨てのスクリプトを書くときなど、ループの条件付けを考えることすら面倒くさいときってありますから(や、そんなときにシェイカー・ソートなんてすること自体ありえないっちゃありえないんですけどね(^^;))。

Permalink | 2004/03/17 09:00


Cha.への伝言板

ボケでもツッコミでもご自由に。質問がある方もこちらへどうぞ。
でも、仮名で結構ですからお名前くらい教えてくださいね