Perlのsort関数は
sort BLOCK LIST
というようにBLOCKを指定すると、そのBLOCK内部で$aと$bという変数同士の比較方法を指定することができる。
なので、そこにprint文を埋め込んでしまえば、sort関数の中で「対象となるLISTのどの要素とどの要素が比較されているのか」が把握できる。
例えば簡単なものだと
$ perl -le 'print sort { print "$a, $b"; $a <=> $b } 0..9'
0, 1
2, 3
4, 5
6, 7
8, 9
0, 2
2, 1
0, 4
4, 1
4, 2
4, 3
6, 8
8, 7
0, 6
6, 1
6, 2
6, 3
6, 4
6, 5
0123456789
$ perl -le 'print sort { print "$a, $b"; $a <=> $b } reverse 0..9'
9, 8
7, 6
5, 4
3, 2
1, 0
8, 6
8, 7
6, 4
6, 5
2, 0
2, 1
4, 0
4, 1
4, 2
4, 3
0123456789というカンジで。
既にsortされているものより逆順になっているものの方が比較回数少なくなるんだ。へぇ〜。
で、せっかくだからどこで比較が起こっているのかをより分かりやすく可視化してみようかと思って、こんなワンライナーを書いてみた。
perl -MList::Util=shuffle -le '@_ = sort { print map { $_==$a->[0] ? "a" : $_==$b->[0] ? "b" : "-" } 0..$n-1; $a->[1] <=> $b->[1] } map [$n++, $_], shuffle 1..pop' <size>ちょっと長くなっちゃった。まぁスペースとか幾らか詰められるけど。
$ perl -MList::Util=shuffle -le '@_=sort{print map{$_==$a->[0]?a:$_==$b->[0]?b:"-"}0..$n-1;$a->[1]<=>$b->[1]}map[$n++,$_],shuffle 1..pop' 8
ab------
--ab----
----ab--
------ab
-ab-----
-a-b----
a--b----
----a--b
----a-b-
-----ab-
--a----b
-b-----a
b------a
a---b---
a-----b-
---a--b-引数で指定した配列のサイズに合わせて、毎回の比較操作の度に$aと$bがどの数字なのかを文字列のインデックスで表現した。
なるほど、最初に0番目と1番目、次は2番目と3番目を比較しているのか、というのが分かりやすく(？)なる
もうちょい
$ perl -MList::Util=shuffle -le '@_=sort{print map{$_==$a->[0]?a:$_==$b->[0]?b:"-"}0..$n-1;$a->[1]<=>$b->[1]}map[$n++,$_],shuffle 1..pop' 16
ab--------------
--ab------------
----ab----------
------ab--------
--------ab------
----------ab----
------------ab--
--------------ab
a-b-------------
a--b------------
-a-b------------
-----a-b--------
----b--a--------
----a-b---------
--a--b----------
--a----b--------
a------b--------
-b-----a--------
---b---a--------
---a--b---------
---ab-----------
--------a-b-----
---------ba-----
---------a-b----
------------a--b
-------------b-a
--------a---b---
----------b-a---
-----------ba---
---------b--a---
---------a---b--
---------a-----b
---------a----b-
-----a--b-------
-----a----b-----
--a-------b-----
b---------a-----
a----------b----
a-----------b---
-a----------b---
-------b----a---
-------a-----b--
------b------a--
---b---------a--
---a-----------b
----b----------a比較が行われている範囲が細かい部分からだんだん全体に広がっている、いかにもmerge sortっぽい動きが分かる気がする。
試しにsortをquick sortに切り替えてみよう。
$ perl -Msort=_qsort -MList::Util=shuffle -le '@_=sort{print map{$_==$a->[0]?a:$_==$b->[0]?b:"-"}0..$n-1;$a->[1]<=>$b->[1]}map[$n++,$_],shuffle 1..pop' 16
------ab--------
-------ab-------
------a-b-------
-----ab---------
----a-b---------
---a--b---------
--a---b---------
-a----b---------
a-----b---------
------a--b------
------a---b-----
------a----b----
------a-----b---
------a------b--
------a-------b-
------a--------b
-------b---a----
-----a--b-------
--------ab------
----a---b-------
--------a-b-----
--------a---b---
--------a----b--
--------a-----b-
--------a------b
---a----b-------
--a-----b-------
-a------b-------
a-------b-------
----ab----------
-----a----b-----
----a-----b-----
---ab-----------
--a-b-----------
-a--b-----------
a---b-----------
----a-------b---
----a--------b--
----a---------b-
----a----------b
b------------a--
-------------ba-
b-------------a-
----------a--b--
----------a---b-
-a----------b---
-ba-------------
--ba------------
-b-a------------
---a--------b---
--b--a----------
-b---a----------
--b------------a
-----b---------aうは、全然挙動が違う！
ピボットが固定されて、両側のものと比較している様子が何となくイメージできそう！
