帰ってきたネコブログ

Twitterのタイムラインに、
「マージソート」ってキーワードが流れてきたので、想像で書いてみた。

想像っていうと嘘になっちゃうんだけど、
たしか、正月あたりに「大人のピタゴラスイッチ」って番組で、
しめじを使って説明してた気がしたので、
あとは、タイムラインで見つけたいくつかのヒントを元に実装してみた。

ヒントはこんな感じ。
・再帰する
・省メモリ（らしい）
・「マージする」という言葉から連想

で、こうなった。

use strict;
use warnings;
use integer;
use v5.10;

say join( ',', my_sort(4,7,2,5,3,1,9,8,6) );

sub my_sort {
    my @ary = @_;
    merge_sort( \@ary, 2 );
    return @ary;
}

sub merge_sort {
    my ( $ary_ref, $n ) = @_;

    print "---- n = $n ----\n";
    dump_array( $ary_ref, $n );

    my $cnt = scalar( @{$ary_ref} );
    for (my $i=0; $i<$cnt; $i+=$n) {

        my $a1 = $i;
        my $b1 = $i + ($n / 2);
        my $a2 = $a1 + ($n / 2);
        my $b2 = $b1 + ($n / 2);

        if ( $cnt <= $b1 ) {
            last; # マージすべきグループがない
        }

        # 2グループのケツの添え字をクリップ
        $b2 = $cnt if ( $cnt < $b2 );

        # マージ先の選択
        for (my $j=$b1; $j<$b2; $j++) {
            say 'merge: ', $ary_ref->[$j];
            for (my $k=$a1; $k<$b2; $k++) {
                if ( $ary_ref->[$k] < $ary_ref->[$j] ) {
                    my $wk = $ary_ref->[$j];
                    for (my $l=$j; $k<$l; $l--) {
                        swap( $ary_ref, $l, $l - 1 );
                    }

                    dump_array( $ary_ref, $n );

                    # マージ先グループの次の要素は、
                    # マージしようとしている値と同じか、より小さい
                    last;
                }
            } 
        }
    }

    print "----  end  ----\n\n";

    if ( $n < scalar(@{$ary_ref}) ) {
        merge_sort( $ary_ref, $n * 2 );
    }
}

sub swap {
    my ( $ary_ref, $a, $b ) = @_;
    my $wk = $ary_ref->[$b];
    $ary_ref->[$b] = $ary_ref->[$a];
    $ary_ref->[$a] = $wk;
}

sub dump_array {
    my ( $ary_ref, $n ) = @_;
 
    my $cnt = scalar( @{$ary_ref} );
    my $i = 0;
    while ( $cnt ) {
        print '[';
        for (my $j=0; $j<$n; $j++) {
            if ( 0 < $cnt ) {
                print $ary_ref->[$i++];
                $cnt--;
                if ( 0 < $cnt and $j < ($n - 1) ) {
                    print ',';
                }
            }   
        }
        print ']';
    }

    print "\n";
}

結果は、こんな感じ。
$ perl aaa.pl
---- n = 2 ----
[4,7][2,5][3,1][9,8][6]
merge: 7
[7,4][2,5][3,1][9,8][6]
merge: 5
[7,4][5,2][3,1][9,8][6]
merge: 1
merge: 8
---- end ----

---- n = 4 ----
[7,4,5,2][3,1,9,8][6]
merge: 5
[7,5,4,2][3,1,9,8][6]
merge: 2
merge: 9
[7,5,4,2][9,3,1,8][6]
merge: 8
[7,5,4,2][9,8,3,1][6]
---- end ----

---- n = 8 ----
[7,5,4,2,9,8,3,1][6]
merge: 9
[9,7,5,4,2,8,3,1][6]
merge: 8
[9,8,7,5,4,2,3,1][6]
merge: 3
[9,8,7,5,4,3,2,1][6]
merge: 1
---- end ----

---- n = 16 ----
[9,8,7,5,4,3,2,1,6]
merge: 6
[9,8,7,6,5,4,3,2,1]
---- end ----

9,8,7,6,5,4,3,2,1

日付が変わる前を目標に勢いで書いたので自信ないけど、
一応、ソートできたので載せておきます。

おしまい。

2013/09/06 追記
マージ先の探索範囲を狭くしていかないとアレですね。
という訳で、そのうち、ちゃんと調べてから書いてみようと思います。

カテゴリー: Perl, コンピューター by ネコ on 2013年09月05日 | タグ: アルゴリズム > ソート > メモ