3.5 安定なソートをPythonで解いてみた

はじめに

「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」の各問題をPythonを用いて解いていくシリーズです。

このシリーズについて

問題

トランプのカードを整列しましょう。ここでは、４つの絵柄(S, H, C, D)と９つの数字(1, 2, ..., 9)から構成される計 36 枚のカードを用います。例えば、ハートの 8 は"H8"、ダイヤの 1 は"D1"と表します。
バブルソート及び選択ソートのアルゴリズムを用いて、与えられた N 枚のカードをそれらの数字を基準に昇順に整列するプログラムを作成してください。アルゴリズムはそれぞれ以下に示す疑似コードに従うものとします。数列の要素は 0 オリジンで記述されています。

https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/all/ALDS1_2_C

BubbleSort(C, N)
   for i = 0 to N-1
     for j = N-1 downto i+1
       if C[j].value < C[j-1].value
         C[j] と C[j-1] を交換

SelectionSort(C, N)
  for i = 0 to N-1
    minj = i
    for j = i to N-1
      if C[j].value < C[minj].value
        minj = j
    C[i] と C[minj] を交換

また、各アルゴリズムについて、与えられた入力に対して安定な出力を行っているか報告してください。ここでは、同じ数字を持つカードが複数ある場合それらが入力に出現する順序で出力されることを、「安定な出力」と呼ぶことにします。（※常に安定な出力を行うソートのアルゴリズムを安定なソートアルゴリズムと言います。）

https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/all/ALDS1_2_C

解法

import random
import time


def bubble_sort(n_list):
    start = time.time()
    swap_count = 0
    # Pythonは参照渡しであるので、新規オブジェクトを作成しないと元のリストが変更される
    sorted_list = list(n_list)
    for i in range(len(sorted_list)):
        for j in reversed(range(i + 1, len(sorted_list))):
            if sorted_list[j][1] < sorted_list[j - 1][1]:
                swap_count += 1
                tmp = sorted_list[j]
                sorted_list[j] = sorted_list[j - 1]
                sorted_list[j - 1] = tmp

    print("swap_count", swap_count)
    print("elapsed_time:{0}".format(time.time() - start))
    return sorted_list


def selection_sort(n_list):
    start = time.time()
    swap_count = 0
    # Pythonは参照渡しであるので、新規オブジェクトを作成しないと元のリストが変更される
    sorted_list = list(n_list)

    for i in range(len(sorted_list)):
        min_j = i
        for j in range(i, len(sorted_list)):
            if sorted_list[j][1] < sorted_list[min_j][1]:
                min_j = j
        if i != min_j:
            swap_count += 1
            tmp = sorted_list[i]
            sorted_list[i] = sorted_list[min_j]
            sorted_list[min_j] = tmp

    print("swap_count", swap_count)
    print("elapsed_time:{0}".format(time.time() - start))
    return sorted_list

数字を基準に整列せよという問題なので、n_list[j][1] < n_list[min_j][1]の所で[1]を付けています。それ以外は3.3,3.4で作成したコードと同じです。

また、ソートが安定かどうかを判定する計算量O(n⁴)の関数を作成しました。

def is_stable(in_list, out_list):
    start = time.time()
    for i in range(len(in_list)):
        for j in range(i + 1, len(in_list)):
            for a in range(len(in_list)):
                for b in range(a + 1, len(in_list)):
                    if (
                        # in_list内に数字部分が同じ値があって,
                        in_list[i][1] == in_list[j][1]
                        # in_list[i]の値とin_list[j]の値の順番がout_list内で逆転していたら
                        and in_list[i] == out_list[b]
                        and in_list[j] == out_list[a]
                    ):
                        # それは安定でないソートである
                        print("False!!")
                        print("i", i)
                        print("j", j)
                        print("a", a)
                        print("b", b)
                        print("in_list_i", in_list[i])
                        print("in_list_j", in_list[j])
                        print("out_list_b", out_list[b])
                        print("out_list_a", out_list[a])
                        print("-------------")
                        return False
    print("elapsed_time:{0}".format(time.time() - start))
    return True

実装を見ただけではなぜこれで安定かどうかを判定できるのか分かりづらいかも知れないので、軽くこのソートが安定かどうかを判定する関数について説明します。

「ソートが安定である」とは、ソートする前と後で、ソートに使ったキー以外の要素の順番が変わらないことを意味します。これをチェックしたいので、ソートされる配列の中で数字部分が同じである要素同士の順序が同じであるかどうかを調べます。
具体的にどのように調べるかというと、常にi < jであるiとj,常にa < bであるaとbを用意し、in_list[i]==out_list[b]、in_list[j]==out_list[a]が成立してしまっている組み合わせが無いかを調べます。in_listの中では必ずjの要素が後に来るはずなのに、out_listの中では先に来てしまっている場合は安定でないと判定するということです。

テストと実行速度測定

テストケース1.ランダム状態からのソート

以下を実行。アルファベットと数字の組み合わせリストを作成し、random.shuffle()でリストをランダム化。それをバブルソートと選択ソートにかけ、安定であるかどうかをチェックする。

def make_card_list():
    n_list = []
    for string in ["S", "H", "C", "D"]:
        for num in range(1, 10):
            n_list.append(string + str(num))
    random.shuffle(n_list)
    return n_list

n_list = make_card_list()
# バブルソートのチェック
orig_sort = bubble_sort(n_list)
print(n_list)
print(orig_sort)
is_stable(n_list, orig_sort)


# 選択ソートのチェック
orig_sort = selection_sort(n_list)
print(n_list)
print(orig_sort)
is_stable(n_list, orig_sort)

結果

バブルソート

バブルソートは安定なソートであることが確認できた。

選択ソート

選択ソートは離れた位置にある数同士を交換するため、安定なソートではない。この例でも安定なソート結果にはならなかった。

テストケース2.降順状態からのソート

ケース1と同様の手法でリストを作成し、.sort(reverse=True)で降順にソートをかけた。それをバブルソートと選択ソートにかけ、安定であるかどうかをチェックする。

n_list = make_card_list()
n_list.sort(reverse=True)

# バブルソートのチェック
orig_sort = bubble_sort(n_list)
print(n_list)
print(orig_sort)
is_stable(n_list, orig_sort)

# 選択ソートのチェック
orig_sort = selection_sort(n_list)
print(n_list)
print(orig_sort)
is_stable(n_list, orig_sort)

結果

バブルソート

やはり安定な結果となった。

選択ソート

安定ではない。

テストケース3.昇順状態からのソート

ケース1と同様の手法でリストを作成し、.sort()で昇順にソートをかけた。それをバブルソートと選択ソートにかけ、安定であるかどうかをチェックする。

n_list = make_card_list()
n_list.sort()

# バブルソートのチェック
orig_sort = bubble_sort(n_list)
print(n_list)
print(orig_sort)
is_stable(n_list, orig_sort)

# 選択ソートのチェック
orig_sort = selection_sort(n_list)
print(n_list)
print(orig_sort)
is_stable(n_list, orig_sort)

結果

バブルソート

選択ソート

バブルソートは安定、選択ソートは安定でない結果になった。

まとめ

バブルソートは常に安定なソートであるが、選択ソートはそうではない。

感想

安定であるか否かをチェックする関数が計算量が多く実行に時間がかかってしまう。バブルソートが常に安定なソートであることを踏まえると、バブルソートの結果との比較で安定であるかどうかチェックしたほうがいいかも知れない。