帰ってきたネコブログ

挿入ソートの改良版であるシェルソートを書いてみた。

use strict;
use warnings;
use v5.10;
use Time::HiRes qw/time/;
use Benchmark qw/cmpthese/;

{
    my @data = 1..2000;
    printf( "--- asc (size = %d)---\n", scalar(@data) );

    {
        my $st = time();
        my @sorted = shell_sort( @data );
        say 'shell :',  time() - $st;
    }

    {
        my $st = time();
        my @sorted = insert_sort( @data );
        say 'insert:', time() - $st;
    }
}

{
    my @data = reverse 1..50000;
    printf( "--- desc (size = %d)---\n", scalar(@data) );

    {
        my $st = time();
        my @sorted = shell_sort( @data );
        say 'shell :',  time() - $st;
    }

    {
        my $st = time();
        my @sorted = insert_sort( @data );
        say 'insert:', time() - $st;
    }
}

sub shell_sort {
    my @data = @_;

    my $cnt = scalar( @data );
    my $gap = $cnt;
    while ( ($gap = int($gap / 2)) ) {
        for (my $i=$gap; $i<$cnt; $i++) {
            my $wk = $data[$i];
            my $j = $i;
            for (; $gap<=$j; $j-=$gap) {
                if ( $wk <= $data[$j-$gap] ) {
                    last;
                }
                else {
                    $data[$j] = $data[$j-$gap];
                }
            }
       
            $data[$j] = $wk;
        }
    }

    return @data;
}

sub insert_sort {
    my @data = @_;

    my $cnt = scalar( @data );
    {
        for (my $i=1; $i<$cnt; $i++) {
            my $wk = $data[$i];
            my $j = $i;
            for (; 1<=$j; $j--) {
                if ( $wk <= $data[$j-1] ) {
                    last;
                }
                else {
                    $data[$j] = $data[$j-1];
                }
            }
       
            $data[$j] = $wk;
        }
    }

    return @data;
}

結果はこんな感じ。
$ perl aaa.pl
--- asc (size = 2000)---
shell :0.0280210971832275
insert:1.30933809280396
--- desc (size = 50000)---
shell :0.788571834564209
insert:0.0688240528106689

挿入ソートとの違いは、ソースを比較すると分かると思うけど、
まず、飛ばし飛ばしで挿入ソートを行って、
その間隔を狭めながら挿入ソートを繰り返して、
最後は通常の挿入ソートを行っている。

最初は、こんなんで速くなるのかと思ったけど、
あまりにも改善され過ぎてて、あとでバグを見つけて直すかも知れない。(*1)(*2)
あと、書いてる最中に、ソート済みのデータに弱いんじゃ？と思って、
試してみた所、案の定、挿入ソートに負けている。

ただ、今回実装したシェルソートは、まだ改善の余地があるらしいけど、
次回は、なぜ、こんなに速いのか？を紐解いてみようと思う。

続く。

(*1) 公開した直後にバグを見つけたので直した。
(*2) その数十分後にバグを見つけたので直した。

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