ソートアルゴリズムの安定性

安定ソート

安定ソート(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が不安定なソートであることがわかる。