シェルソートをPerlで実装してみた - wanwan_bowwow

シェルソート

シェルソート（Shellsort）は、in-placeな比較ソートのアルゴリズムの一種である。シェルソートは、バブルソートあるいは挿入ソートの一般化と見なすことができる。ソートの方法は、まず、間隔の離れた要素の組に対してソートを行い、だんだんと比較する要素間の間隔を小さくしながらソートを繰り返す、というものである。離れた場所の要素からソートを始めることで、単純に近くの要素を比較する場合よりも速く、要素を所定の位置に移動させることができる。ただし、安定ソートではない。

アルゴリズム

基本的な部分は、挿入ソートと同じである。挿入ソートは「ほとんど整列されたデータに対しては高速」という特長があるものの、「隣り合った要素同士しか交換しない」ため、あまり整列されていないデータに対しては低速であった。そのため、適当な間隔をあけた飛び飛びのデータ列に対してあらかじめソートしておき、挿入ソートを適用すれば高速になると考えられる。この考え方を適用したのがシェルソートである。

１.適当な間隔 h を決める
２.間隔 h をあけて取り出したデータ列に挿入ソートを適用する
３.間隔 h を狭めて、2.を適用する操作を繰り返す
４.h=1 になったら、最後に挿入ソートを適用して終了

適切な間隔

シェルソートでは、間隔 h の決め方が重要になってくる。同じ位置の要素ばかりが選択される状況を避け、数値がよく混ざり合うような間隔 h を設定する。「h^(n+1) = 3h^(n) + 1」という条件で選び出した数列を選択すると高速化できる。

具体例

■入力
1 行目に整数 n が与えられます。続く n 行目に n 個の整数 Ai(i=0,1,...,n−1) が与えられます。

■出力
3 行目に、sub insertion_sort を用いた場合のプログラムが終了した直後の cnt の値を出力してください。
続く n 行に整列した Ai(i=0,1,...,n−1) を出力してください。

■制約
1 ≤ n ≤ 1,000,000
0 ≤ Ai ≤ 109

■入力例

■出力例

use strict;
use warnings;
use utf8;
binmode(STDOUT, ":utf8");
use Time::HiRes qw( usleep gettimeofday tv_interval );

&main;

sub main {
    print "数列の長さを表す整数を入力してください。\n";
    my $input_num_length = <STDIN>;

    print "整数を改行区切りで1つずつ入力してください。入力完了後、endと入力してください\n";
    my @input_lines_arr;

    while (my $input_int = <STDIN>) {
        last if $input_int eq "end\n";
        chomp($input_int);
        push(@input_lines_arr, $input_int);
    }

    my ($m, $output_g, $cnt, $input_lines_arr) = &shell_sort($input_num_length, @input_lines_arr);

    print $m;
    foreach (@{$output_g}) {
        print $_;
    }
    print $cnt;
    foreach (@{$input_lines_arr}) {
        print $_;
    }
}

sub shell_sort {
    my ($input_num_length, @input_lines_arr) = @_;

    $\="\n";
    my $cnt = 0;
    my $m = 2;
    my @g = (4, 1);
    my $input_lines_arr;

    for (my $i = 0; $i < $m; $i++) {
        ($cnt, $input_lines_arr) = &insertion_sort($input_num_length, \@input_lines_arr, $g[$i], $cnt);
        @input_lines_arr = @{$input_lines_arr};
    }
    my @output_g = join(' ', @g);
    return ($m, \@output_g, $cnt, $input_lines_arr);
}

sub insertion_sort {
    my ($input_num_length, $input_lines_arr, $g, $cnt) = @_;

    my @input_lines_arr = @{$input_lines_arr};

    for (my $i = $g; $i < $input_num_length; $i++) {
        my $v = $input_lines_arr[$i];
        my $j = $i - $g;

        while ($j >= 0 && $input_lines_arr[$j] > $v) {
            $input_lines_arr[$j + $g] = $input_lines_arr[$j];
            $j = $j - $g;
            $cnt++;
        }
        $input_lines_arr[$j + $g] = $v;
    }
    return ($cnt, \@input_lines_arr);
}

[hogefuga@localhost:sort_algorithm]$ perl shell_sort.pl
数列の長さを表す整数を入力してください。
5
整数を改行区切りで1つずつ入力してください。入力完了後、endと入力してください。
5
1
4
3
2
end
2
4 1
3
1
2
3
4
5

参考:
シェルソート - Wikipedia
Aizu Online Judge