# Ruby&Perlでマージソート

require 'pp'

def merge_sort(a, p = 1, r = a.length)
def merge(a, p, q, r)
n1 = q - p + 1
n2 = r - q
left = Array.new
right = Array.new
(1..n1).each{|i|
left[i-1] = a[(p + i - 1) - 1]
}
(1..n2).each{|j|
right[j-1] = a[(q + j) - 1]
}
left[n1] = 1.0/0
right[n2] = 1.0/0
i = 1
j = 1
(p..r).each{|k|
if left[i-1] <= right[j-1]
a[k-1] = left[i-1]
i = i +1
else
a[k-1] = right[j-1]
j = j +1
end
}
end
if p < r
q = ((p + r) / 2).to_i
merge_sort(a, p, q)
merge_sort(a, q+1, r)
merge(a,p,q,r)
end
return a
end

pp merge_sort([9,1,3,4,5])
pp merge_sort([3,1,3,2,5,1])


## 追記

perlでもなんとなく書いてみた。リファレンスの使い方とか忘れていて手間どった。

use strict;
use warnings;

sub merge_sort {
sub merge {
my ($a,$p, $q ,$r) = @_;
my $n1 =$q - $p + 1; my$n2 = $r -$q;
my @left = ();
my @right = ();
foreach ((1..$n1)) {$left[$_ - 1] = @$a[($p +$_ - 1) - 1];
}
foreach ((1..$n2)) {$right[$_ - 1] = @$a[($q +$_) - 1];
}
$left[$n1] = 10000;
$right[$n2] = 10000;
print "left : [", join(",", @left), "], ",
"right : [", join(",", @right), "].", "\n";
my $i = 1; my$j = 1;
foreach my $k ($p..$r){ if ($left[$i-1] <=$right[$j-1]) { @$a[$k-1] =$left[$i -1];$i++;
} else {
@$a[$k-1] = $right[$j-1];
$j++; } } return$a;
}
my ($a,$p, $r) = @_; if ($p < $r) { my$q = int(($p +$r) / 2);
print "split array [", join(',',@$a[$p-1..$r-1]), "] into [", join(',',@$a[$p-1..$q-1]), "] and [",
join(',',@$a[$q+1-1..$r-1]), "].\n"; &merge_sort($a, $p,$q);
&merge_sort($a,$q + 1, $r); &merge($a, $p,$q, $r); } return$a;
}

my @a = (1,5,3,10,5,2,1);
print "before sorting : [", join(",",@a), "].\n";
print "=" x 50, "\n";
&merge_sort(\@a, 1, 7);
print "=" x 50, "\n";
print "After sorting : [", join(",",@a), "].\n";


ついでに分割&統治されていく様子をprintしてみた。

/tmp% perl hoge.pl
before sorting : [1,5,3,10,5,2,1].
==================================================
split array [1,5,3,10,5,2,1] into [1,5,3,10] and [5,2,1].
split array [1,5,3,10] into [1,5] and [3,10].
split array [1,5] into [1] and [5].
left : [1,10000], right : [5,10000].
split array [3,10] into [3] and [10].
left : [3,10000], right : [10,10000].
left : [1,5,10000], right : [3,10,10000].
split array [5,2,1] into [5,2] and [1].
split array [5,2] into [5] and [2].
left : [5,10000], right : [2,10000].
left : [2,5,10000], right : [1,10000].
left : [1,3,5,10,10000], right : [1,2,5,10000].
==================================================
After sorting : [1,1,2,3,5,5,10].


## メモ

• マージソートは分割統治のアルゴリズムの代表例
• 最小の単位になるまで分割
• 最小単位になったらそこからmergeを開始
• mergeしていく中で、左と右に分けて、左と右が常に整列された状態を保つ
• そうすることでmergeのときに右の先頭と左の先頭しか見ないでいい状態を作り出す
• 計算量としてはとなる
• 分割していくので、漸化式が出てくる
• 統治のところがcn
• これがであることを見て行く

• 作者: T.コルメン,R.リベスト,C.シュタイン,C.ライザーソン,Thomas H. Cormen,Clifford Stein,Ronald L. Rivest,Charles E. Leiserson,浅野哲夫,岩野和生,梅尾博司,山下雅史,和田幸一
• 出版社/メーカー: 近代科学社
• 発売日: 2007/03
• メディア: 単行本
• 購入: 13人 クリック: 378回
• この商品を含むブログ (60件) を見る