Ruby&Perlでマージソート

数学的基礎とデータ構造 (アルゴリズムイントロダクション)のp28付近にあるマージソートをRubyでそのまま書きくだす簡単なお仕事。2行で書けるとかそんなの知るか。

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
• これがであることを見て行く

数学的基礎とデータ構造 (アルゴリズムイントロダクション)