帰ってきたネコブログ

挿入ソートは、既にソート済みのデータ列に、
ソートした状態を維持しながらデータを追加するのは早いそうなので、
何種類かデータ列を用意して、ソートに掛かる時間を計測してみました。

という訳で、ランダムと昇順と降順の3種類を用意しました。

use strict;
use warnings;
use v5.10;

use Array::Shuffle qw/shuffle_array/;

print "\n--- random data ---\n";
{
    my @data = 1..9;
    shuffle_array( @data );
    say join( ', ', @data );
    say join( ', ', insert_sort(@data) );
}

print "\n--- 9,8,7 ... (descending order) ---\n";
{
    my @data = reverse( 1..9 );
#    shuffle_array( @data );
    say join( ', ', @data );
    say join( ', ', insert_sort(@data) );
}

print "\n--- 1,2,3 ... (ascending order) ---\n";
{
    my @data = 1..9;
#    shuffle_array( @data );
    say join( ', ', @data );
    say join( ', ', insert_sort(@data) );
}

sub insert_sort {
    my @data = @_;

    my $move = 0;
    my $cnt = scalar( @data );
    for (my $i=1; $i<$cnt; $i++) {
        if ( $data[$i] < $data[$i-1] ) {
            printf( "i =%2d: skip!\n", $i );
        }
        else {
            my $wk = $data[$i];
            $move++;
            my $j = $i;
            for (; 0<$j; $j--) {
                if ( $wk <= $data[$j-1] ) {
                    last;
                }
                else {
                    $data[$j] = $data[$j-1];
                    $move++;
                }
            }

            $data[$j] = $wk;
            $move++;

            printf( "i =%2d: insert!\n", $i );
        }
    }

    printf( "move = %d\n", $move );

    return @data;
}

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

--- random data ---
7, 6, 4, 3, 5, 1, 8, 9, 2
i = 1: skip!
i = 2: skip!
i = 3: skip!
i = 4: insert!
i = 5: skip!
i = 6: insert!
i = 7: insert!
i = 8: insert!
move = 24
9, 8, 7, 6, 5, 4, 3, 2, 1

--- 9,8,7 ... (descending order) ---
9, 8, 7, 6, 5, 4, 3, 2, 1
i = 1: skip!
i = 2: skip!
i = 3: skip!
i = 4: skip!
i = 5: skip!
i = 6: skip!
i = 7: skip!
i = 8: skip!
move = 0
9, 8, 7, 6, 5, 4, 3, 2, 1

--- 1,2,3 ... (ascending order) ---
1, 2, 3, 4, 5, 6, 7, 8, 9
i = 1: insert!
i = 2: insert!
i = 3: insert!
i = 4: insert!
i = 5: insert!
i = 6: insert!
i = 7: insert!
i = 8: insert!
move = 52
9, 8, 7, 6, 5, 4, 3, 2, 1

入れ替えが必要かどうかチェックして、
“skip!” or “insert!”を出力させています。
あと、データの移動回数を数えて、最後にその合計を出力しました。

移動回数の合計は、何回かこれを繰り返して、
平均をとって比較するのが良いと思います。

続く。

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