«     «

マージソート（？）を書いてみた

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

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

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

で、こうなった。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
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日 | タグ: > >

Leave a Comment

  • 2025年5月
    月 火 水 木 金 土 日
     1234
    567891011
    12131415161718
    19202122232425
    262728293031  

    固定ページ

    カテゴリー

    アーカイブ

    検索

    SNS

    メタ情報