ソートアルゴリズムの安定性
安定ソート
安定ソート(stable sort)とは、ソート(並び替え)のアルゴリズムのうち、同等なデータのソート前の順序が、ソート後も保存されるものをいう。つまり、ソート途中の各状態において、常に順位の位置関係を保っていることをいう。
use strict; use warnings; use utf8; binmode(STDOUT, ":utf8"); &input_cards; sub input_cards { print "カードの枚数を表す整数を入力してください。\n"; my $input_num_cards = <STDIN>; print "個別のカードを空白区切りで入力してください。\n"; my $input_cards_lines = <STDIN>; chomp($input_cards_lines); my @cards_lines_arr = split(/ /, $input_cards_lines); &stable_sort($input_num_cards, @cards_lines_arr); } sub stable_sort { my ($input_num_cards, @cards_lines_arr) = @_; &bubble_sort($input_num_cards, @cards_lines_arr); &selection_sort($input_num_cards, @cards_lines_arr); } # 安定なソート sub bubble_sort { my ($input_num_cards, @cards_lines_arr) = @_; $\="\n"; for (my $i = 0; $i < $input_num_cards; $i++) { for (my $j = $input_num_cards - 1; $j > $i; $j--) { my $j_num_minus1 = substr($cards_lines_arr[$j - 1], 1, 3); my $j_num = substr($cards_lines_arr[$j], 1, 3); if ($j_num_minus1 > $j_num) { my $tmp = $cards_lines_arr[$j - 1]; $cards_lines_arr[$j - 1] = $cards_lines_arr[$j]; $cards_lines_arr[$j] = $tmp; } } } my @output_lines_arr = join(' ', @cards_lines_arr); print @output_lines_arr; } # 不安定なソート sub selection_sort { my ($input_num_cards, @cards_lines_arr) = @_; $\="\n"; for (my $i = 0; $i < $input_num_cards; $i++) { my $minj = $i; for (my $j = $input_num_cards - 1; $j > $i; $j--) { my $j_num = substr($cards_lines_arr[$j], 1, 3); my $minj_num = substr($cards_lines_arr[$minj], 1, 3); if ($minj_num > $j_num) { $minj = $j; } } if ($cards_lines_arr[$i] eq $cards_lines_arr[$minj]) { next; } my $tmp = $cards_lines_arr[$i]; $cards_lines_arr[$i] = $cards_lines_arr[$minj]; $cards_lines_arr[$minj] = $tmp; } my @output_lines_arr = join(' ', @cards_lines_arr); print @output_lines_arr; }
[hogefuga@localhost:sort_algorithm]$ perl stable_sort.pl カードの枚数を表す整数を入力してください。 5 個別のカードを空白区切りで入力してください。 H4 C9 S4 D2 C3 D2 C3 H4 S4 C9 D2 C3 S4 H4 C9
出力結果から、bubble_sortが安定なソートでselection_sortが不安定なソートであることがわかる。