[ruby-list:43504] Re: ブロックとともに呼び出されたsortについて

naruse です。

Toshiyuki Ogura さんは書きました:
> ブロックの中で
> a[1] <=> b[1]
> としているので、何かと何かの2つのものを比較しているように見えます。
> このようなとき、sortのレシーバが、キーと値のペアが3組以上あるハッシュ
> や、要素が3個以上ある配列の場合はこの式はどうなるのでしょうか。
3個のうちの、どれか一つがaに、また別のどれかがbに入ります。
例えば、
 [1,2,3,4,5].sort{|a,b| p([a,b]); a<=>b}
としてみると、手元では
 [1, 3]
 [3, 5]
 [2, 3]
 [4, 3]
 [4, 5]
 [1, 2]
と出力されました。
このように、2つの要素を何度か比較して、最終的にsortを行っています。

なぜこれで sort ができるのかは、Wikipediaあたりで調べてください。
Rubyではクイックソートが用いられているそうです。
http://ja.wikipedia.org/wiki/%E3%82%AF%E3%82%A4%E3%83%83%E3%82%AF%E3%82%BD%E3%83%BC%E3%83%88

参考までに array.c のソースも、qsort ってのが見えますね。
static VALUE
sort_internal(ary)
    VALUE ary;
{
    struct ary_sort_data data;

    data.ary = ary;
    data.ptr = RARRAY(ary)->ptr; data.len = RARRAY(ary)->len;
    qsort(RARRAY(ary)->ptr, RARRAY(ary)->len, sizeof(VALUE),
          rb_block_given_p()?sort_1:sort_2, &data);
    return ary;
}
src/ruby/branches/ruby_1_8/array.c: unmodified: line 1619 of 3065 [52%]

> sortのブロックの中で使われる
> a[1] <=> b[1]
> は、どう理解すれば分かりやすいのでしょうか。
> この場合、難しく考えないで、理屈抜きで、ソートするときは
> a[1] <=> b[1]
> のように書く、と覚えていても差し支えないでしょうか。
 {"x" => 1, "y" => 0, "z" => 2}.sort{|a,b| a[1] <=> b[1]}
は
 [["x", 1], ["y", 0], ["z", 2]].sort{|a,b| a[1] <=> b[1]}
と書き換えられるわけですが、ここでのa[1], b[1]は、
sortしているarrayの要素 (例えば["x", 1]) の、
2個目の要素 (例えば1) 同士を比較しているわけで、
これはすなわち、元の hash それぞれの key => value の組の、
value 同士を比較している、という意味です。

理屈抜きで覚えると複雑なソートをしたくなった時に困るかと。

-- 
NARUSE, Yui  <[e-mail]>
DBDB A476 FDBD 9450 02CD 0EFC BCE3 C388 472E C1EA