「なっとくアルゴリズム」を読んだ - 分割統治 -

前回に続いて「なっとくアルゴリズム」を読んで理解したことのまとめです。

www.kato-eng.info

www.kato-eng.info

分割統治

分割統治は問題の解決に取り組むための新しい切り口を与えてくれる。分割統治を利用したアルゴリズムとしてはクイックソートが有名。

分割統治法は、そのままでは解決できない大きな問題を小さい問題に分割し、その全てを解決することで最初の問題全体を解決するという手法である。

分割統治を利用したプログラム例

数値の配列が渡されると、全ての数値を足して合計を返す関数をループを利用すると下記のようになる。

# Python
def sum(array):
    total = 0
    for x in array:
        total += x
    return total

print(sum([1, 2, 3, 4]))

しかし、これを再帰関数でプログラムしようとすると次のような考え方になる。

ステップ1 基本ケースを特定する

最も単純な配列を考えるとそれは要素が0、または1個の配列と考えられるので、これを基本ケースとする。

ステップ2 問題の規模を縮小する

再帰呼出しの度に空の配列に近づいていく必要がある。

sum([1, 2, 3, 4])  == 10

1 + sum([2, 3, 4]) == 1 + 9 == 10

sum再帰関数に渡すリストは上記のどちらの場合でも結果は10となる。しかし下の記述の方がsum再帰関数に渡すリストは小さくなっている。つまり問題の規模が縮小したといえる。

再帰関数を実際に実装すると下記のようになる。

# Python

def sum(array):
    if array == []:
        return 0
    return array[0] + sum(array[1:])

print(sum([1, 2, 3, 4]))

クイックソート

クイックソートのアルゴリズムは分割統治の考え方を使用している。クイックソートの考え方としては下記のようになる。

ステップ1 ピボットを選ぶ

ソート対象のリストとして「[4, 2, 1, 3, 5]」が渡されたとする。クイックソートを行うにはまず、リストから要素を1つ取り出します。この取り出した要素をピボットと呼ぶ。

良いピボットの選び方はリストからランダムに選ぶことだが、ここでは単純に先頭要素をピボットとして取り出すことにする。

ステップ2 配列のパーティショニングを行う

ピボットを選んだら次はピボットよりも小さい要素と大きい要素を見つけ出します。これをパーティショニングと呼ぶ。この時点では次の3つの要素があることになる。

1. ピボットよりも小さい数を全て含んだ部分リスト
2. ピボット
3. ピボットよりも大きい数を全て含んだ部分リスト

2つの部分リストはこの時点ではソートされておらず、パーティショニングが行われただけである。

しかし、これらの部分リストがソート済であれば、

[ピボットよりも小さい数のリスト] + ピボット + [ピボットよりも大きい数のリスト]

の要領でリストを結合するとソート済のリストが得られることになる。

この時点では次のような結果になる。

ピボットより小さい数のリスト = [2, 1, 3]
ピボット = 4
ピボットより大きい数のリスト = [5]

ステップ3 2つの部分配列でクイックソートを再帰的に呼び出す

「ピボットよりも小さい数を全て含んだ部分リスト」と「ピボットよりも大きい数を全て含んだ部分リスト」それぞれに対し、再帰的にクイックソートを呼び出す。

Pythonでクイックソートの再帰関数を実装すると下記のようになる。

def quicksort(array):
    # 基本ケース
    if len(array) < 2:
        return array
    # 再帰ケース
    else:
        pivot = array[0]
        # ピボットより小さい数の部分リスト
        less = [i for i in array[1:] if i <= pivot]
        # ピボットより大きい数の部分リスト
        greater = [i for i in array[1:] if i > pivot]
        return quicksort(less) + [pivot] + quicksort(greater)

print(quicksort([4, 2, 1, 3, 5]))