選択ソートをPerlで実装してみた
選択ソート
選択ソート(selection sort)は、ソートのアルゴリズムの一つ。配列された要素から、最大値やまたは最小値を探索し配列最後の要素と入れ替えをおこなうこと。最悪計算時間がO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、しばしば用いられる。
データ列中で一番小さい値を探し、1番目の要素と交換する。次に、2番目以降のデータ列から一番小さい値を探し、2番目の要素と交換する。これを、データ列の最後まで繰り返す(厳密には、データ列の最後より1つ手前までの繰り返しでよい。一つ前まで交換済みであれば、最後(残り)は必ず最大値になるからである)。大小が入れ替わる降順の場合も同様の手法である。
■入力
入力の最初の行に、数列の長さを表す整数 N が与えられます。2行目に、N 個の整数が空白区切りで与えられます。
■出力
出力は 2 行からなります。1行目に整列された数列を 1 行に出力してください。数列の連続する要素は1つの空白で区切って出力してください。2 行目に交換回数を出力してください。
■制約
1 ≤ N ≤ 100
0 ≤ A の要素 ≤ 100
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); &selection_sort($input_num_length, @input_lines_arr); } sub selection_sort { my ($input_num_length, @input_lines_arr) = @_; $\="\n"; my $flag = 0; for (my $i = 0; $i < $input_num_length; $i++) { my $minj = $i; for (my $j = $i; $j < $input_num_length; $j++) { if ($input_lines_arr[$j] < $input_lines_arr[$minj]) { $minj = $j; } } if ($input_lines_arr[$i] == $input_lines_arr[$minj]) { next; } my $tmp = $input_lines_arr[$i]; $input_lines_arr[$i] = $input_lines_arr[$minj]; $input_lines_arr[$minj] = $tmp; $flag++; } my @output_lines_arr = join(' ', @input_lines_arr); print @output_lines_arr; print $flag; }
[hogefuga@localhost:sort_algorithm]$ perl selection_sort.pl 数列の長さを表す整数を入力してください。 6 整数を空白区切りで入力してください。 5 2 4 6 1 3 1 2 3 4 5 6 3