挿入ソートをPerlで実装してみた

挿入ソート

挿入ソート(insertion sort)は、ソートのアルゴリズムの一つ。整列してある配列に追加要素を適切な場所に挿入すること。平均計算時間・最悪計算時間がともにO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、しばしば用いられる。安定な内部ソート。

まず0番目と1番目の要素を比較し、順番が逆であれば入れ換える。次に、2番目の要素が1番目までの要素より小さい場合、正しい順に並ぶように「挿入」する(配列の場合、前の要素を後ろに一つずつずらす)。この操作で、2番目までのデータが整列済みとなる(ただし、さらにデータが挿入される可能性があるので確定ではない)。このあと、3番目以降の要素について、整列済みデータとの比較と適切な位置への挿入を繰り返す。


■入力
入力の最初の行に、数列の長さを表す整数 N が与えられます。2 行目に、N 個の整数が空白区切りで与えられます。

■出力
出力は N 行からなります。挿入ソートの各計算ステップでの途中結果を 1 行に出力してください。配列の要素は1つの空白で区切って出力してください。最後の要素の後の空白など、余計な空白や改行を含めると Presentation Error となりますので注意してください。

■制約
1 ≤ N ≤ 100
0 ≤ A の要素 ≤ 1,000

Aizu Online Judge


use strict;
use warnings;
use utf8;
binmode(STDOUT, ":utf8");

&input_nums;

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

    print "整数を空白区切りで入力してください。\n";
    my $input_lines = <STDIN>;

    chomp($input_lines);
    my @input_lines_arr = split(/ /, $input_lines);

    &insertion_sort($input_num_length, @input_lines_arr);
}

sub insertion_sort {
    my ($input_num_length, @input_lines_arr) = @_;
    $\="\n";

    for (my $i = 0; $i < $input_num_length; $i++) {
        my @output_lines_arr = join(' ', @input_lines_arr);
        print @output_lines_arr;
        return if $i + 1 == $input_num_length;

        if ($input_lines_arr[$i] < $input_lines_arr[$i + 1]) {
            next;
        }

        for (my $j = 0; $j < $input_num_length; $j++) {
            if ($input_lines_arr[$j] < $input_lines_arr[$i + 1]) {
                next;
            }
            my @fixed_arr = grep $_ != $input_lines_arr[$i + 1], @input_lines_arr;
            splice(@fixed_arr, $j, 0, $input_lines_arr[$i + 1]);
            @input_lines_arr = @fixed_arr;
            last;
        }
    }
}


[hogefuga@localhost:sort_algorithm]$ perl insertion_sort.pl
数列の長さを表す整数を入力してください。
6
整数を空白区切りで入力してください。
5 2 4 6 1 3
5 2 4 6 1 3
2 5 4 6 1 3
2 4 5 6 1 3
2 4 5 6 1 3
1 2 4 5 6 3
1 2 3 4 5 6



修正版(2018.10.20)

sub insertion_sort {
    my ($input_num_length, @input_lines_arr) = @_;
    $\="\n";

    for (my $i = 0; $i < $input_num_length; $i++) {
        my $v = $input_lines_arr[$i];
        my $j = $i - 1;
        
        while ($j >= 0 && $input_lines_arr[$j] > $v) {
            $input_lines_arr[$j + 1] = $input_lines_arr[$j];
            $j--;
        }
        
        $input_lines_arr[$j + 1] = $v;
        my @output_lines_arr = join(' ', @input_lines_arr);
        print @output_lines_arr;
    }
}