バブルソートをPerlで実装してみた
バブルソート
バブルソート (bubble sort) は、ソートのアルゴリズムの一つ。隣り合う要素の大小を比較しながら整列させること。最悪計算時間がO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、また並列処理との親和性が高いことから、しばしば用いられる。安定な内部ソート。
全ての要素に関して、隣接する要素と比較し順序が逆であれば入れ替える。これを要素数-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); &bubble_sort($input_num_length, @input_lines_arr); } sub bubble_sort { my ($input_num_length, @input_lines_arr) = @_; $\="\n"; my $flag = 0; for (my $i = 0; $i < $input_num_length; $i++) { for (my $j = $input_num_length - 1; $j > $i; $j--) { if ($input_lines_arr[$j - 1] > $input_lines_arr[$j]) { my $tmp = $input_lines_arr[$j - 1]; $input_lines_arr[$j - 1] = $input_lines_arr[$j]; $input_lines_arr[$j] = $tmp; $flag++; } } } my @output_lines_arr = join(' ', @input_lines_arr); print @output_lines_arr; print $flag; }
[hogefuga@localhost:sort_algorithm]$ perl bubble_sort.pl 数列の長さを表す整数を入力してください。 5 整数を空白区切りで入力してください。 5 3 2 4 1 1 2 3 4 5 8
気づいたこと
$j + 1にするより$j - 1 にした方が良い。$j + 1にすると、$j + 1が$input_num_lengthに一致する場合繰り返しを終了するという条件文が必要になるので。