帰ってきたネコブログ

毎日、何か書こうとすると、やっぱネタ切れしちゃうんだけど、
タイミング良くソート期を迎えたので、
マージソートを書くために段階を踏んでみようと思います。

ソートの性質として、安定と不安定なものがあって、
そういうのを説明するためにも、
とりあえず、挿入ソートを実装してみました。

2013/09/07 追記
カンペを見たら間違っていたので、書き直しました。

use strict;
use warnings;
use v5.10;

main();

sub main {
    my @data = 1..9;

    # シャッフル
    my $n = scalar( @data );
    for ( 1..100 ) {
        my $a = int( rand $n );
        my $b = int( rand $n );
        @data[$a,$b] = @data[$b,$a];
    }

    say '';
    say join( ', ', @data );
    say '';
    say "---- start ----\n";

    @data = insert_sort( @data );

    say "----  end  ----\n";
    say join( ', ', @data );
}

sub insert_sort {
    my @data = @_;

    my $cnt = scalar( @data );
    for (my $i=1; $i<$cnt; $i++) {
        printf( "\$i = %2d\n", $i );
        dump_array( \@data, $i );

        my $wk = $data[$i];
        my $j = $i;
        for (; 0<$j; $j--) {
            if ( $wk <= $data[$j-1] ) {
                last;
            }
            else {
                $data[$j] = $data[$j-1];
                dump_array( \@data, ($i + 1), ($j - 1) );
            }
        }

        $data[$j] = $wk;
        dump_array( \@data, ($i + 1) );

        print "\n";
    }

    return @data;
}

sub dump_array {
    my ( $ary_ref, $sorted_cnt ) = @_;
    my $invalid_index = $_[2] // -1;

    my $cnt = scalar( @{$ary_ref} );
    my $i = 0;

    print '[';
    for (; $i<$sorted_cnt; $i++) {
        print ( ($i == $invalid_index) ? 'x' : $ary_ref->[$i] );
        print ', ' if $i < ($sorted_cnt - 1);
    }
    print ']';
    print ' ' if $i < $cnt;

    for (; $i<$cnt; $i++) {
        print $ary_ref->[$i];
        print ', ' if $i < ($cnt - 1);
    }

    print "\n";
}

実行結果はこんな感じ。
$ perl bbb.pl

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

---- start ----

$i = 1
[5] 9, 3, 1, 2, 7, 6, 4, 8
[x, 5] 3, 1, 2, 7, 6, 4, 8
[9, 5] 3, 1, 2, 7, 6, 4, 8

$i = 2
[9, 5] 3, 1, 2, 7, 6, 4, 8
[9, 5, 3] 1, 2, 7, 6, 4, 8

$i = 3
[9, 5, 3] 1, 2, 7, 6, 4, 8
[9, 5, 3, 1] 2, 7, 6, 4, 8

$i = 4
[9, 5, 3, 1] 2, 7, 6, 4, 8
[9, 5, 3, x, 1] 7, 6, 4, 8
[9, 5, 3, 2, 1] 7, 6, 4, 8

$i = 5
[9, 5, 3, 2, 1] 7, 6, 4, 8
[9, 5, 3, 2, x, 1] 6, 4, 8
[9, 5, 3, x, 2, 1] 6, 4, 8
[9, 5, x, 3, 2, 1] 6, 4, 8
[9, x, 5, 3, 2, 1] 6, 4, 8
[9, 7, 5, 3, 2, 1] 6, 4, 8

$i = 6
[9, 7, 5, 3, 2, 1] 6, 4, 8
[9, 7, 5, 3, 2, x, 1] 4, 8
[9, 7, 5, 3, x, 2, 1] 4, 8
[9, 7, 5, x, 3, 2, 1] 4, 8
[9, 7, x, 5, 3, 2, 1] 4, 8
[9, 7, 6, 5, 3, 2, 1] 4, 8

$i = 7
[9, 7, 6, 5, 3, 2, 1] 4, 8
[9, 7, 6, 5, 3, 2, x, 1] 8
[9, 7, 6, 5, 3, x, 2, 1] 8
[9, 7, 6, 5, x, 3, 2, 1] 8
[9, 7, 6, 5, 4, 3, 2, 1] 8

$i = 8
[9, 7, 6, 5, 4, 3, 2, 1] 8
[9, 7, 6, 5, 4, 3, 2, x, 1]
[9, 7, 6, 5, 4, 3, x, 2, 1]
[9, 7, 6, 5, 4, x, 3, 2, 1]
[9, 7, 6, 5, x, 4, 3, 2, 1]
[9, 7, 6, x, 5, 4, 3, 2, 1]
[9, 7, x, 6, 5, 4, 3, 2, 1]
[9, x, 7, 6, 5, 4, 3, 2, 1]
[9, 8, 7, 6, 5, 4, 3, 2, 1]

---- end ----

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

（ここまで追記）

<strong>#if(0) /* ここから間違い */</strong>

use strict;
use warnings;
use v5.10;

main();

sub main {
    my @data = 1..9;

    # シャッフル
    my $n = scalar( @data );
    for ( 1..100 ) {
        my $a = int( rand $n );
        my $b = int( rand $n );
        @data[$a,$b] = @data[$b,$a];
    }

    say '';
    say join( ', ', @data );
    say '';
    say "---- start ----\n";

    @data = insert_sort( @data );

    say "----  end  ----\n";
    say join( ', ', @data );
}

sub insert_sort {
    my @data = @_;

    my $cnt = scalar( @data );
    for (my $i=1; $i<$cnt; $i++) {
        printf( "\$i = %2d\n", $i );
        dump_array( \@data, $i );

        for (my $j=0; $j<$i; $j++) {
            if ( $data[$j] < $data[$i] ) {
                print $data[$j], ' < ', $data[$i], ' ? true.',
                      " insert ${data[$i]} to \$data[${j}].\n";
                my $wk = $data[$i];
                for (my $k=$i; $j<$k; $k--) {
                    $data[$k] = $data[$k-1];
                }

                $data[$j] = $wk;
                last;
            }
        }

        print "\n";
    }

    return @data;
}

sub dump_array {
    my ( $ary_ref, $sorted_cnt ) = @_;

    my $cnt = scalar( @{$ary_ref} );
    my $i = 0;

    print '[';
    for (; $i<$sorted_cnt; $i++) {
        print $ary_ref->[$i];
        print ', ' if $i < ($sorted_cnt - 1);
    }
    print ']';
    print ' ' if $i < $cnt;

    for (; $i<$cnt; $i++) {
        print $ary_ref->[$i];
        print ', ' if $i < ($cnt - 1);
    }

    print "\n";
}

実行結果はこんな感じ。
$ perl aaa.pl

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

---- start ----

$i = 1
[5] 8, 6, 9, 3, 4, 1, 2, 7
5 < 8 ? true. insert 8 to $data[0].

$i = 2
[8, 5] 6, 9, 3, 4, 1, 2, 7
5 < 6 ? true. insert 6 to $data[1].

$i = 3
[8, 6, 5] 9, 3, 4, 1, 2, 7
8 < 9 ? true. insert 9 to $data[0].

$i = 4
[9, 8, 6, 5] 3, 4, 1, 2, 7

$i = 5
[9, 8, 6, 5, 3] 4, 1, 2, 7
3 < 4 ? true. insert 4 to $data[4].

$i = 6
[9, 8, 6, 5, 4, 3] 1, 2, 7

$i = 7
[9, 8, 6, 5, 4, 3, 1] 2, 7
1 < 2 ? true. insert 2 to $data[6].

$i = 8
[9, 8, 6, 5, 4, 3, 2, 1] 7
6 < 7 ? true. insert 7 to $data[2].

---- end ----

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

シャッフルも実装したので、無駄に行数があるんだけど、
がんばって、ソート後と未ソートのデータが区別できるように表示しました。

<strong>#endif /* ここまで間違い */</strong>

ちなみに、挿入ソートは安定だそうです。

おしまい。

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