帰ってきたネコブログ

Perlのソートはマージソートらしいので性質は安定なのですが、
その性質を確認する方法を調べてみようと思います。

まずは、ありがちなソートから。

use strict;
use warnings;
use v5.10;

my @w = qw/0 0 1 1 1 2 2/;
my @v = qw/a b c d e f g/;

my @data = ();
while ( @w ) {
    push @data, [ shift @w, shift @v ];
}

say '-- before --';
say join ',', (map { $_->[1] } @data);

say '-- after  --';
@data = shuffle( @data );
say join ',', (map { $_->[1] } @data);

say '-- sorted --';
@data = sort { $a->[0] <=> $b->[0] } @data;
say join ',', (map { $_->[1] } @data);

sub shuffle {
    my @data = @_;

    my $n = scalar @data;
    foreach my $i ( 0..($n - 1) ) {
        my $j = int( rand $n );
        @data[$i,$j] = @data[$j,$i];
    }

    return @data;
}

実行結果はこんな感じ。
$ perl aaa.pl
-- before --
a,b,c,d,e,f,g
-- after --
d,e,c,b,g,a,f
-- sorted --
b,a,d,e,c,g,f

何がダメって、シャッフルがダメですね。
これじゃ、ソートの性質が分からないです。

なので、安定なシャッフルを実装します。

use strict;
use warnings;
use v5.10;

my @w = qw/0 0 1 1 1 2 2/;
my @v = qw/a b c d e f g/;

my @data = ();
while ( @w ) {
    push @data, [ shift @w, shift @v ];
}

say 'before';
say join ',', (map { $_->[1] } @data);

say 'after';
@data = shuffle( @data );
say join ',', (map { $_->[1] } @data);

say 'sorted';
@data = sort { $a->[0] <=> $b->[0] } @data;
say join ',', (map { $_->[1] } @data);

sub shuffle {
    my @tmp = @_;

    my @src = ();
    while ( @tmp ) {
        my @wk = ( shift @tmp );
        if ( @tmp ) {
            while ( $wk[0]->[0] == $tmp[0]->[0] ) {
                push @wk, ( shift @tmp );
                last unless @tmp;
            }
        }

        push @src, \@wk;
    }

    my @dst = ();
    while ( @src ) {
        my $i = int( rand scalar(@src) );
        push @dst, shift $src[$i];
        if ( scalar(@{$src[$i]}) == 0 ) {
            @src = grep { @{$_}; } @src;
        }
    }

    return @dst;
}

実行結果はこんな感じ。
$ perl bbb.pl
before
a,b,c,d,e,f,g
after
f,c,d,g,e,a,b
sorted
a,b,c,d,e,f,g

これなら、元に戻りますね。
元に戻るということは、ソートの性質が安定であることを意味します。

でも、このままじゃ、
「安定なシャッフルって何ですか？日本語おかしくないですか？」
ってなりますよね？？

そう、安定なシャッフルなんて日本語はさっき思い付いたし、
そもそも、シャッフルなんかしてません。
正確に表現するなら、マージですね。
ソート時の重み単位でグループ分けをして、
ランダムに選んだグループの先頭から要素を取り出して並べています。
一見、シャッフルされているように見えるけど、
グループ単位ではソートされたままです。

という訳で、今回実装したshuffleは、
ソート済みの配列が入力されることを想定しているので、
n回ソートするみたいな芸当はできないですが、
ソートの性質を探るには使えそうな気がします。

あと、これに入力するソートされた配列も自動生成したいですね。

続く。

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