分割征服

2.1 Binary search

にぶんたんさく

パーティション征服

で要素を探してみましょう.😎

[Divide]の真ん中の要素はSを2つのリスト

に分割する.

[Conquer]xが真ん中の要素より大きい場合は右、左より小さく、再帰呼び出し

[Obtain]選択リストから得られた答え

を返す.

Binary search

def location (S, low, high):

    if (low > high):
        return 0

    else:

        mid = (low + high) // 2
        if (x == S[mid]):
            return mid
        elif (x < S[mid]):
            return location(S, low, mid - 1)
        else:
            return location(S, mid + 1, high)

2.2 Merge sort

merge sortもDivide and Conquer😎

[Divide]要素n個のSをn/2個の要素を有する2個のリスト

に分割する.

[Conquer]左側のリストと右側のリストを再帰集計して

に並べ替える.

[Combine]は、2つのソートリストを1つのソートリストに結合し、

を返します.

Merge sort

def mergesort (S):

    n = len(S)
    if (n <= 1):
        return S
    else:
        mid = n // 2
        U = mergesort(S[0 : mid])
        V = mergesort(S[mid : n])
        return merge(U, V)

Merge

def merge(U, V):
    S = []
    i = j = 0
    while (i < len(U) and j < len(V)):
        if (U[i] < V[j]):
            S.append(U[i])
            i += 1
        else:
            S.append(V[j])
            j += 1
        if (i < len(U)):
            S += U[i : len(U)]
        else:
            S += V[j : len(V)]
            return S

以上のソースコードはソートされていますが、入力リストSのほかに、リストUとVの2つ以上を使用する必要があります.

他に作成されたリスト要素の合計数

merge sort()が呼び出されるたびに、新しいUおよびVが生成される.

全再帰呼び出し時、要素の個数=n+n/2+n/4...=2 n

そのため、メモリの使用効率が低下していることをどのように改善しますか?
リストを書かないで、中で並べ替えましょう.

Merge sort 2

def mergesort2 (S, low, high):

    if (low < high):

        mid = (low + high) // 2
        mergesort2(S, low, mid)
        mergesort2(S, mid + 1, high)
        merge2(S, low, mid, high)

Merge 2

def merge2 (S, low, mid, high):
    U = []
    i = low
    j = mid + 1
    while (i <= mid and j <= high):
        if (S[i] < S[j]):
            U.append(S[i])
            i += 1
        else:
            U.append(S[j])
            j += 1
    if (i <= mid):
        U += S[i : mid + 1]
    else:
        U += S[j : high + 1]
    for k in range(low, high + 1):
        S[k] = U[k - low]

2.3分割征服設計方法

分割征服設計ポリシー

分割:問題入力ケースを複数の小入力ケース

に分割する.
征服

:各小さな入力ケースを征服し、小さな入力ケースが十分に小さい場合は

に戻る

統合:必要に応じて、小さな入力ケースの答えを統合することで、元の入力ケースの答え

を得ることができます.

分割征服アルゴリズム

パーティション征服VSダイナミックプランニング
Top-Down vs Bottom-Up

分期征服vs貪欲法
貪欲法は最も効率的な分割征服アルゴリズムですか?
ex.交換ソート(greedy)->一番前の要素と残りの要素を

に分けたと考えられる

2.4クイックソート（パーティション交換ソート）

クイックソート:パーティションとConquer

内部(その場)ソート:他のリスト

を使用する必要はありません.

Quick-Sort

[Divide]基準要素(pivot)を決定し、基準要素を基準として、左右に

を分割する.

[Conquer]クイックソート

、左リストと右リストの間で再帰ソート

[Obtain]ソートのリスト

を返します.

Quick sort

def quicksort (S, low, high):

    if (high > low):

        pivotpoint = partition(S, low, high)
        quicksort(S, low, pivotpoint - 1)
        quicksort(S, pivotpoint + 1, high)

ここの問題は、どうやって分けますか?

ピボットの決定

編まずリストの最初の要素を基準要素

とする.

15単位で、左小、右大に分けます
最初の要素で並べ替えを続行

リストを基本要素に分割する方法

2 2 2つのインデックスi、jを使用して比較および交換

Partition (for Quick Sort)

def partition (S, low, high):

    pivotitem = S[low]
    j = low
    for i in range(low + 1, high + 1):

        if (S[i] < pivotitem):

            j += 1;
            S[i], S[j] = S[j], S[i] # swap

    pivotpoint = j
    S[low], S[pivotpoint] = S[pivotpoint], S[low] # swap
    return pivotpoint

異なるpartition()関数を実現できるか~~

partition()関数の他の実装方法

S = [26, 5, 37, 1, 61, 11, 59, 15, 48, 19]

[26, 5, 37, 1, 61, 11, 59, 15, 48, 19]: 2, 9

[26, 5, 19, 1, 61, 11, 59, 15, 48, 37]: 4, 7

[26, 5, 19, 1, 15, 11, 59, 61, 48, 37]: 6, 5

[11, 5, 19, 1, 15, 26, 59, 61, 48, 37]

前面のエレメントより前後が大きい/小さい
完了したら、中間の要素をpivotpointに変更します.

partition2

def partition2 (S, low, high):

    pivotitem = S[low]
    i = low + 1
    j = high
    while (i <= j):

        while (S[i] < pivotitem):

        i += 1

        while (S[j] > pivotitem):

        j -= 1
        
        if (i < j):

            S[i], S[j] = S[j], S[i] # swap

    pivotpoint = j
    S[low], S[pivotpoint] = S[pivotpoint], S[low] # swap
    return pivotpoint

pivot itemよりも大きな要素が現れるまで左から右へ進みます
右からpivot itemまでより小さな要素が現れるまでjに進みます
jがiの右側にある場合、swapの両方
(右の小さい値、左の大きい値のため)

quicksort 2

def quicksort2 (S, low, high):

    if (high > low):

        pivotpoint = partition2(S, low, high)
        quicksort2(S, low, pivotpoint - 1)
        quicksort2(S, pivotpoint + 1, high)