初めてのコンピュータサイエンス第11章解答

第11章の解答。以下ネタバレなので、読みたくない方は立ち去りましょう。問題文は載せませんので悪しからず。必要なら買いましょう。

1

k回探索するものとすると、ソート+探索と、毎回探索するという計算の量について次の式が成り立つ(定数項がないため、すごく大まかですが)。k*log_2(N) + N*log_2(N) <= k*N*log_2(N)(_2は対数の底が2であることを意味する)。これを満たすkはk >= N/(N-1)である。右辺はN=1のとき最大値2をとり、かつ1より大きい。従ってk>=2であればよく、2回探索した時点で毎回未ソートのリストから探索するよりも、ソートしてから探索を繰り返すほうが高速になる。

2

利用したコードは以下の通り。既存のソートアルゴリズムに毎回print文を挟めばよい。

a)の場合

• [1, 5, 4, 3, 7, 6, 2]
• [1, 2, 4, 3, 7, 6, 5]
• [1, 2, 3, 4, 7, 6, 5]
• [1, 2, 3, 4, 7, 6, 5]
• [1, 2, 3, 4, 5, 6, 7]
• [1, 2, 3, 4, 5, 6, 7]
• [1, 2, 3, 4, 5, 6, 7]
• [1, 2, 3, 4, 5, 6, 7]

b)の場合

• [5, 6, 4, 3, 7, 1, 2]
• [4, 5, 6, 3, 7, 1, 2]
• [3, 4, 5, 6, 7, 1, 2]
• [3, 4, 5, 6, 7, 1, 2]
• [1, 3, 4, 5, 6, 7, 2]
• [1, 2, 3, 4, 5, 6, 7]
• [1, 2, 3, 4, 5, 6, 7]

# -*- encoding: sjis -*-

def selection_sort(L):
    ''' L[:i]までソート済みとして、
        L[i]とL[i:]の最小値の交換を繰り返す
    '''
    for i in range(len(L)):
        smallest = L.index(min(L[i:]))
        L[i], L[smallest] = L[smallest], L[i]
        print L
    return L

def insertion_sort(L):
    ''' L[:b]までソート済みとして、
        L[b]をソート済みのリストに混ぜる
    '''
    for i in range(1, len(L)):
        pos = 0
        for j in range(i-1, -1, -1):
            # print L[i], " ", L[j]
            if L[i] >= L[j]:
                pos = j + 1
                # print "pos = ", pos, L[i], L[j]
                break
        L.insert(pos, L[i])
        del L[i+1]
        print L
    return L

3

テストと実装のファイルは分けずに書いていますが、本当なら分けるべきでしょう。

# -*- encoding: sjis -*-

import nose

def swap(L, pos1, pos2):
    tmp = L[pos1]
    L[pos1] = L[pos2]
    L[pos2] = tmp

def bubble_sort(L):
    ''' 1)先頭から隣り合う要素を比較し、添え字の小さいほうが
          大きいようなら値の交換を行う
        2)1)をi回繰り返すと後ろからi個の要素が整列済みになっている
          要素数-1回繰り返す
    '''
    for i in range(len(L)-1, 0, -1):
        for j in range(i):
            if L[j] > L[j+1]:
                swap(L, j, j+1)
        print L
    return L

# run_test とするとテストケースと勘違いされるのでrun_checkとする
def run_check(original, expected):
    bubble_sort(original)
    assert original == expected

def test_empty():
    run_check([], [])

def test_one():
    run_check([3], [3])

def test_reverse():
    run_check([5, 4, 3, 2, 1], [1, 2, 3, 4, 5])

def test_same():
    run_check([2, 2, 2, 2], [2, 2, 2, 2])

def test_random():
    run_check([6, 5, 4, 3, 7, 1, 2], [1, 2, 3, 4 ,5 , 6, 7])

if __name__ == '__main__':
    nose.runmodule()

4

テストコードは上のテストの使いまわしでよいと思います。

def bubble_sort_2(L):
    ''' 1)最後尾から先頭へ向けて隣り合う要素を比較し、添え字の
          小さいほうが大きいようなら値の交換を行う
        2)1)をi回繰り返すと先頭からi個の要素が整列済みになっている。
          要素数-1回繰り返す
    '''
    for i in range(len(L)-1):
        for j in range(len(L)-1, i, -1):
            if L[j] < L[j-1]:
                swap(L, j, j-1)
        print L

5

用意したデータは降順データなので、全部のデータを反転させることになる。結果としては、バブルソートは全体的に遅いということが分かる。また、ソートにかかる時間はO(n^2)に従っていることが確認できる。バブルソートが特に遅いのは、比較の回数が多いためと思われる。一方挿入ソート、選択ソートで実行速度に大きな差は見られなかった。大量データをずらすというコストは、交換するコストとほとんど差がないのではないかと推測される。なお、ch11_sort_algo.pyに上に挙げたbubble_sortなどのソートアルゴリズムを実装している。

import time
from ch11_sort_algo import *

def print_times(L):
    print len(L),
    for func in (bubble_sort, bubble_sort_2, insertion_sort, selection_sort):
        L_copy = L[:]
        t_from = time.time()
        func(L_copy)
        t_to = time.time()
        print "\t%.1f" % ((t_to - t_from) * 1000.),
    print

for list_size in [10, 1000, 2000, 5000, 10000]:
    L = range(list_size)
    L.reverse()
    print_times(L)

6

ソート済みの長さNのリストの場合

手法	比較回数	コピー回数
挿入ソート	N-1回(毎回ソート済みの最終要素に1度アクセスして終了)	0回(後ろにつけるだけでコピーは発生しない)
選択ソート	N(N-1)/2回(未ソートの部分で最小値探索の必要あり)	0回(未ソート部分の先頭が最小値と分かるのでコピー不要)

リストが逆順

手法	比較回数	コピー回数
挿入ソート	N(N-1)/2回(毎回ソート済みのリスト全体の探索の必要あり)	0回(コピーではなく値の交換がN-1回発生する)
選択ソート	N(N-1)/2回	N-1回(コピーするリストの長さは可変)

入力のリストがすべて同じ値の場合

手法	比較回数	コピー回数
挿入ソート	N-1回(毎回ソート済みの最終要素にアクセスして終了)	0回
選択ソート	N(N-1)/2回	0回

7

挿入に伴い発生するリストのコピーにかかるコストを考慮していない。これを考慮するのであれば、オーダーはN^2になる。全体の結論にも影響する。

8

ランダムに並び替えたものが偶然ソート済みになるのは、要素数がNであれば、平均してN!回に1回発生することなのでO(N!)になる。要素が一意であるかが問題になっているのは、一意かそうでないかでオーダーが変化するからである。例えば、N個のうちN-1個は同じ値で1つだけ違う値であれば、O(N)になるし、すべて同じ値であれば、O(1)になるからである。

9

extend呼び出しをなくすにはループ内で結合まで行うしかない。そこで、i1かi2が終端まで着たら他方をすべて結合してループを抜け出すという書き換えを行った。

# -*- encoding: sjis -*-

def merge(L1, L2):
    newL = []
    i1 = i2 = 0

    while i1 != len(L1) or i2 != len(L2): # and から orに変更
        if i1 >= len(L1): # 終端に着いたので他方の残りの要素を結合
            newL += L2[i2:]
            break
        elif i2 >= len(L2):
            newL += L1[i1:]
            break

        if L1[i1] <= L2[i2]:
            newL.append(L1[i1])
            i1 += 1
        else:
            newL.append(L2[i2])
            i2 += 1

    return newL

def mergesort(L):
    workspace = []
    for i in range(len(L)): # 1要素に分解
        workspace.append([L[i]])

    i = 0

    while i < len(workspace) - 1: # マージ開始
        L1 = workspace[i]
        L2 = workspace[i + 1]
        newL = merge(L1, L2)
        workspace.append(newL)
        i += 2

    if len(workspace) != 0:
        L[:] = workspace[-1][:]

    return L

if __name__ == '__main__':
    data = [3, 0, 2, 3, -1]
    print mergesort(data)
    data = [6, 5, 4, 3, 7, 1, 2]
    print mergesort(data)
    data = []
    print mergesort(data)