▼

便利なソートを使いたいよね

イテレータのソートしようと思ってソートについて調べていた。
ソートのアルゴリズムというと世の中にはいろいろあるものです。
最終的にはマージソートを採用したわけですが、なかなか悩ましいものです。
実際に作って調べてみることにした。例によってPerlで書いてある。@aを数字の大小でソートすることを考えている。

誰でも知っている、というとそれはウソだけど、あまりに有名なのがバブルソート。

my @a=(93,18,11,14,36,86,24,89,82,10,31,33,42,3,0,81,40,40,21,56);
for my $i(0..$#a-1){
  for my $j($i+1..$#a){
    if($a[$i]>$a[$j]){
      my $t=$a[$i];
      $a[$i]=$a[$j];
      $a[$j]=$t;
    }
  }
}

まぁなんでこれでソートできるんだというのはよくわからないものですが、
とにかく手当たり次第順番を入れ替えていくようなアルゴリズムですね。
というわけでとてつもなく遅いと評判。
入れ替え部分をリスト代入で書いてないのはちょっと遅いから。
ランダムな10000個の要素をバブルソートする実験では、実に5000万回の比較と2261万回の入れ替えをしていた。
所要時間は50.77秒と、嫌になるほど時間がかかる。要素数の2乗に比例する時間がかかると言われている。

これと同じく嫌になるほど遅いのが挿入ソート。こちらの方がわかりやすいかも。

for my $i(1..$#a){
  my $c=splice(@a,$i,1);
  my $j=$i;
  for(;$j>0;$j--){
    last if $a[$j-1]<=$c;
  }
  splice(@a,$j,0,$c);
}

前から要素を引っこ抜いて、その引っこ抜いたところから前に順にチェックして、適当なところに挿入すると。
適当なところというのは、前の要素が自分と同じか小さいところですね。
1,3,4,6とあるところに4を入れるなら、今ある4の前がちょうどいいと。そういうことです。
実はバブルソートよりも少し性能がいいらしく、2525万回の比較で済んでいる。
挿入の回数は9999回だが、挿入は入れ替えよりもめんどくさいですからね。
時間はぐっと短縮されて20.06秒。バブルソートがあまりに遅いのは、多分Perlのコードの実行に時間がかかってるからじゃないかなと。
多分Cで作ったものならばそうも差はないんじゃないかな。

選択ソートってのもあるらしい。小さい順に選んでソートするから選択ソートというらしい。

for my $i(0..$#a-1){
  my $min=$i+1;
  for my $j($i+2..$#a){
    $min=$j if $a[$min]>$a[$j];
  }
  ($a[$i],$a[$min])=($a[$min],$a[$i]);
}

0番目の要素を含む右側の要素で最小の要素と0番目の要素を入れ替えて…
というのを最後までやっていくわけですね。
10000個ソートすると5000万回の比較が必要なのはバブルソートと一緒だけど、9999回の入れ替えで済む。
なので入れ替えが遅いときには使えるらしい。
ただし、このソートにはちょっと問題がある。というのも安定ソートではないんですね。
安定ソートというのは等しい要素があったら、元の並び順と一緒になるソートのこと。
等しいというのは比較すれば大きくも小さくもないという意味ね。全く一緒の要素かは知らない。
例えば、小数の配列が与えられて整数部の大小だけでソートするとき。

@a=(6.58 , 4.59 , 3.71 , 7.48 , 6.18 , 4.89 , 4.67 , 1.55 , 5.60 , 4.49);
for my $i(0..$#a-1){
  my $min=$i+1;
  for my $j($i+2..$#a){
    $min=$j if int($a[$min])>int($a[$j]);
  }
  ($a[$i],$a[$min])=($a[$min],$a[$i]);
}

この@aでは整数部が4である小数が4つある。4.59,4.89,4.67,4.49の順にならんでほしい。
しかし実際はこの結果は4.89,4.59,4.67,4.49のように元とは少々違う並びになってしまう。
なんでかといえば、隣の要素以外と入れ替えを行うから。
僕は安定なソートが大好きなので、安定でないソートは使わないことにしよう。

ここからは頭のいいソート。
いろいろあるんだが、特に有名なマージソートとクイックソートだけ。
他にも、バブルソートの改良のコムソートとかあるんだけどね。
まずマージソートですね。マージソートはPerl 5.8以降では標準で使われているようです。
以前Perl 5.6から使われてるとか書いたような気がするけど、間違っていたようです。
マージソートはクイックソートよりは遅いかも知れないけど、悪くないというわけで評判らしい。

sub msort{
  return @_ if(@_==1);
  my $m=int(@_/2);
  my @a=msort(@_[0..$m-1]);
  my @b=msort(@_[$m..$#_]);
  my @r=();
  while(@a && @b){
    if($a[0]<$b[0]){ push(@r,shift(@a)); }
    else           { push(@r,shift(@b)); }
  }
  return (@r,@a,@b);
}
@a=msort(@a);

再帰でやりますよ。やり方は簡単で半分に分割して、それぞれをソートする。
そしてそのソートした半分ずつを、頭から小さい方を選んで引っこ抜いていくと。
例えば7,1,5,2,8,6,3,9と並んでたら、半分に割ってソートにかけると。
すると1,2,5,7と3,6,8,9が得られるので、始めの要素同士を比較して小さい1をまず選ぶと。
次に2,5,7と3,6,8,9となって、2が選ばれ、次に5,7と3,6,8,9となって3が選ばれて…
とやっていくと、前のグループが全部選ばれて、後ろのグループの8,9が残ってしまう。
そこまで来れば、今まで並べた分に余りをくっつければ終わり。
最後の気味の悪い(@r,@a,@b)は、@rに@aと@bをくっつけるということが書いてある。
@aか@bは全部無くなってるはずだから、残った方をくっつけるという意味になりますよね。
なんて感じですばらしく高速です。なんと12万回の比較で済みます。所要時間は0.23秒と比べものにならないぐらい速い。
100万個の要素の並び替えも現実的な時間でできてしまった。所要時間は45.86秒、1867万回の比較で済んでいる。
非常に要素数が多ければ有利なソートですね。まぁ少なくても悪くはないと思いますけど。
このソートのいいところは、ただ半分に割ってそれぞれを別々に計算してくっつけるだけなので並列処理に向くそうだ。
なので実際はもっともっと速くできるかもしれない。
そんなに仕組みも難しくないしいいですね。
ただ欠点は、並び替えのためにデータとは別にメモリを食うこと。
まぁ今のコンピュータで気にするところではないですけど。

最後にクイックソート。速いと評判だが、実に難しい。

sub qsort{
  return @_ if(@_<2);
  my $p=$_[rand(@_)];
  my ($l,$r)=(0,$#_);
  while(1){
    for(;$_[$l]<$p;$l++){}
    for(;$_[$r]>$p;$r--){}
    last if($l>=$r);
    ($_[$l],$_[$r])=($_[$r],$_[$l]);
    $l++; $r--;
  }
  qsort(@_[0 ..$l-1]);
  qsort(@_[$r+1..$#_]);
  return @_;
}
@a=qsort(@a);

実は理屈はそうは難しくないんですよ。適当な値を選んで、それより小さいのと大きいのに分けて、
それぞれでソートするだけです。適当な値は配列中からランダムに選んでる。
問題はその小さいのと大きいのに分けるところです。
ここで賢い方法を考えてやったら上に書いたようになるのだが、これ両端から見ていくのね。
なので安定ソートではありません。
それと問題なのが、適当な値の選び方なんですね。適当な値をいい加減に選ぶとえらいことになります。
だから要素数が少ないときは他のソートを使うと速いしうまくいくと。
というわけでこんな方法で実験してみた。

sub mysort{
  return @_        if(@_<2);
  return qsort(@_) if(@_>8);
  for my $i(1..$#_){
    for(my $j=$i;$j>0;$j--){
      last if $_[$j-1]<=$_[$j];
      ($_[$j-1],$_[$j])=($_[$j],$_[$j-1]);
    }
  }
  return @_;
}
sub qsort{
  return @_ if(@_<2);
  my $p=$_[rand(@_)];
  my ($l,$r)=(0,$#_);
  while(1){
    for(;$_[$l]<$p;$l++){}
    for(;$_[$r]>$p;$r--){}
    last if($l>=$r);
    ($_[$l],$_[$r])=($_[$r],$_[$l]);
    $l++; $r--;
  }
  mysort(@_[0 ..$l-1]);
  mysort(@_[$r+1..$#_]);
  return @_;
}
qsort(@a);

mysortでは8要素以下は挿入ソートでソートしている。
ちなみにこの挿入ソートはspliceを使っていない。まぁこれがよくある例です。
これだと10000個のソートは0.19秒でやる。比較回数は16万回ですね。
挿入ソート併用しない場合0.22秒程度かかってるので、いくらか速くなってるのは確か。
100万個だと、37.86秒で261万回の比較を行っている。
マージソートよりは速いことがわかる。

しかし結局マージソートにしたのは、クイックソートがめんどくさいというのが大きいのだけど、
マージソートは来たデータから順番に処理していけるんですね。
イテレータで順番に読んでいくとき、2つ受け取って並び替えて、2つのブロックが2つできたら、
その2つのブロックをソートしてくっつけて4つのブロック、同様にして4つのブロックができたら8つに…
ということができて楽しいからマージソートにした。
ちなみにクイックソートが安定でないというのはこのような入れ替えで前後に分けた場合であって、
それ以外の方法では安定なソートになることもあります。
そんな方法もまた調べてみようかな。