rubyのsort_by / shuffle から学ぶシュワルツ変換とフィッシャー - イェーツのシャッフル

ffakerのsourceを眺めていたら以下のようなコードがありました。

# ffaker-2.1.0/lib/ffaker/utils/array_utils.rb
module FFaker
  module ArrayUtils

    def self.shuffle(array)
      array.sort_by{Kernel.rand}
    end

これ自体は、Array#shuffleがない頃のrubyでshuffleさせるためのものですが
意味は分かりやすいし読みやすいのですが、
ふと sort_by {rand} という書き方に一瞬、あれ？これどうなってるんだっけと
思ってしまいました。

シュワルツ変換

randの結果を突っ込んだ「tupleを生成してsortして、tupleにした元の結果を返す」
というアルゴリズムです。
これをSchwartzian Transform と言います。
シュワルツ（シュウォーツ）変換 (Schwartzian Transform) : Serendip - Webデザイン・プログラミング

stack overflowでの解説

How does Ruby's sort_by {rand} work? - Stack Overflow
このroughなrubyコードを用いた説明がわかりやすいです。
そして、最後にArray#shuffle!はFisher-Yatesを用いてより最適化してまっせと教えてくれてます。

Fisher-Yates shuffle

Programming Place Plus　アルゴリズムとデータ構造編【その他】　第２章　ランダムシャッフル
こちらの解説がわかりやすかったです。

配列全体の中から１つの要素をランダムで選び出し、 
これを末尾の要素と交換することを繰り返します。 
ここで、"末尾" の位置は、交換を行うごとに１つずつ手前へ移動していきます。 
言い換えれば、後ろの方から確定させていくということになります。

sorce

ruby2.3.0

> $ Array#shuffle!

From: array.c (C Method):
Owner: Array
Visibility: public
Number of lines: 29

static VALUE
rb_ary_shuffle_bang(int argc, VALUE *argv, VALUE ary)
{
    VALUE *ptr, opts, *snap_ptr, randgen = rb_cRandom;
    long i, snap_len;

    if (OPTHASH_GIVEN_P(opts)) {
    randgen = rb_hash_lookup2(opts, sym_random, randgen);
    }
    if (argc > 0) {
    rb_raise(rb_eArgError, "wrong number of arguments (%d for 0)", argc);
    }
    rb_ary_modify(ary);
    i = RARRAY_LEN(ary);
    ptr = RARRAY_PTR(ary);
    snap_len = i;
    snap_ptr = ptr;
    while (i) {
    long j = RAND_UPTO(i);
    VALUE tmp;
    if (snap_len != RARRAY_LEN(ary) || snap_ptr != RARRAY_PTR(ary)) {
        rb_raise(rb_eRuntimeError, "modified during shuffle");
    }
    tmp = ptr[--i];
    ptr[i] = ptr[j];
    ptr[j] = tmp;
    }
    return ary;
}

このwhileのとこですね。