挿入ソートを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; } }