1

私はアルゴリズムの本 (Intro to algorithms 3rd edition Cormen) でマージソート (インプレース) について読んでいましたが、Python で実装することにしました。問題は、自分が間違っていることを見つけられないことです... C++ でいくつかのコードを見ましたが、それでも修正できません。

これが私のコードです：

def MERGE(A,start,mid,end):
    L=[0]*(mid - start + 1)
    for i in range(len(L) - 1):
        L[i] = A[start+i]
    L[len(L) - 1] = 100000 # centinel, (fix)
    R=[0]*(end - mid + 2)
    for j in range(len(R) - 1):
        R[j] = A[mid+j]

    R[len(R) - 1] = 100000
    i = 0
    j = 0
    k = start
    for l in range(k,end):
        if(L[i] < R[j]):
            A[l] = L[i]
            i = i + 1
        else:
            A[k] = R[j]
            j = j + 1   

def mergeSort(A,p,r):
    if p < r:
        mid = int((p+r)/2)
        mergeSort(A,p,mid)
        mergeSort(A,mid+1,r)
        MERGE(A,p,mid,r) 

A  = [20, 30, 15, 21, 42, 45, 31, 0, 9]
mergeSort(A,0,len(A)]

コードを実行すると、いくつかのインデックスの問題が発生します。

File "myrealmerge.py", line 9, in MERGE
R[j] = A[mid+j]
IndexError: list index out of range

これは「ばかげた質問」であり、関連する投稿があることは知っていますが、そこにある提案を試してみましたが、うまくいきません...

誰でも私を助けることができますか？ありがとうございます！

4

3 に答える 3

7

This code works fine:

def MERGE(A,start,mid,end):
    L = A[start:mid]
    R = A[mid:end]
    i = 0
    j = 0
    k = start
    for l in range(k,end):
        if j >= len(R) or (i < len(L) and L[i] < R[j]):
            A[l] = L[i]
            i = i + 1
        else:
            A[l] = R[j]
            j = j + 1  

def mergeSort(A,p,r):
    if r - p > 1:
        mid = int((p+r)/2)
        mergeSort(A,p,mid)
        mergeSort(A,mid,r)
        MERGE(A,p,mid,r)

A  = [20, 30, 21, 15, 42, 45, 31, 0, 9]
mergeSort(A,0,len(A))
print A

I tried to minimize the change from your code.

Good luck!

(Added)

You can check the dividing process by using this code.

def MERGE(A,start,mid,end):
    # Do nothing
    pass

def mergeSort(A,p,r):
    if r - p > 1:
        mid = int((p+r)/2)
        print A[p:mid],A[mid:r]
        mergeSort(A,p,mid)
        mergeSort(A,mid,r)
        MERGE(A,p,mid,r)

A  = [20, 30, 21, 15, 42, 45, 31, 0, 9]
mergeSort(A,0,len(A))

The result is as follows:

[20, 30, 21, 15] [42, 45, 31, 0, 9]
[20, 30] [21, 15]
[20] [30]
[21] [15]
[42, 45] [31, 0, 9]
[42] [45]
[31] [0, 9]
[0] [9]

This is what we want. However, 'mid+1' makes invalid result. Here is the test code:

def MERGE(A,start,mid,end):
    # Do nothing
    pass

def mergeSort(A,p,r):
    if r - p > 1:
        mid = int((p+r)/2)
        print A[p:mid],A[mid+1:r]    # Changed
        mergeSort(A,p,mid)
        mergeSort(A,mid+1,r)         # Changed
        MERGE(A,p,mid,r)

A  = [20, 30, 21, 15, 42, 45, 31, 0, 9]
mergeSort(A,0,len(A))

result:

[20, 30, 21, 15] [45, 31, 0, 9]
[20, 30] [15]
[20] []
[45, 31] [9]
[45] []

(Added)

Here is a code using 'mid+1':

# New indexing function that includes the right index.
def get_partial_list(origin_list, left_index, right_index): # Added
    return origin_list[left_index:right_index+1]


def MERGE(A,start,mid,end):
    L = get_partial_list(A,start,mid)
    R = get_partial_list(A,mid+1,end)
    i = 0
    j = 0
    k = start
    for l in range(k,end+1):            # changed
        if j >= len(R) or (i < len(L) and L[i] < R[j]):
            A[l] = L[i]
            i = i + 1
        else:
            A[l] = R[j]
            j = j + 1  

def mergeSort(A,p,r):
    if r - p > 0:                          # changed
        mid = int((p+r)/2)
        mergeSort(A,p,mid)
        mergeSort(A,mid+1,r)             # changed
        MERGE(A,p,mid,r)

A  = [20, 30, 21, 15, 42, 45, 31, 0, 9]
mergeSort(A,0,len(A)-1)                 # changed
print A

I've added new indexing function. Is this the code you expected?

于 2013-09-30T03:33:53.957 に答える
1

lancif と krishna Prasad が提供するソリューションには、スペースの複雑さ O(1) がありません。

これは、スペースの複雑さがO（1）のPy3のマージソートのアルゴリズムです。メイン関数sort_imergeは、2 つの補助関数wmergeと を使用しwsortます。

このソリューションは、次で説明した C コードに基づいています: その他の SO トピックおよび適切な C 実装について また、doctests を使用した完全な Python コードを見つけることができます 。

def sort_imerge(Seq, l=0, u=None):
    """ Merge sorting, mutable input. 
    Input sequence changed in place. 

    Time: O(n * log n)
        log n -- levels
        n -- elements on each level must be merged

    Space (additional): O(1) 
        input changed in place

    Returns None

    """
    u = len(Seq) if u is None else u
    if  u - l > 1:
        m = l + (u - l) // 2
        w = l + u - m  
        wsort(Seq, l, m, w)
        while w - l > 2:
            n = w
            w = l + (n - l + 1) // 2
            wsort(Seq, w, n, l)
            wmerge(Seq, l, l + n - w, n, u, w)
        n = w
        while n > l: # fallback to insert sort
            for m in range(n, u):
                if Seq[m-1] > Seq[m]:
                    Seq[m-1], Seq[m] = Seq[m], Seq[m-1]
            n -= 1

def wmerge(Seq, i, m, j, n, w):
    """Merge subarrays [i, m) and [j, n) into work area w.
    All indexes point into Seq.
    The space after w must be enough to fit both subarrays.
    """
    while i < m and j < n:
        if Seq[i] < Seq[j]:
            Seq[i], Seq[w] = Seq[w], Seq[i]
            i += 1
        else:
            Seq[j], Seq[w] = Seq[w], Seq[j]
            j += 1
        w += 1
    while i < m:
        Seq[i], Seq[w] = Seq[w], Seq[i]
        i += 1
        w += 1
    while j < n:
        Seq[j], Seq[w] = Seq[w], Seq[j]
        j += 1
        w += 1

def wsort(Seq, l, u, w):
    """Sort subarray [l, u) and put reuslt into work area w.
    All indexes point into Seq.
    """
    if  u - l > 1:
        m = l + (u - l) // 2
        sort_imerge(Seq, l, m)
        sort_imerge(Seq, m, u)
        wmerge(Seq, l, m, m, u, w)
    else:
        while l < u:
            Seq[l], Seq[w] = Seq[w], Seq[l]
            l +=1
            w +=1
于 2019-06-16T15:21:05.827 に答える
0

配列を再帰的に左右の部分に分割し、要件に従ってマージします。つまり、ASC以下DESCのコードを確認してください。

def merge_sort(a):
    if len(a) <= 1:
        return a

    left = [];
    right = [];

    mid = len(a)/2

    left = a[0:mid]
    right = a[mid:(len(a))]

    print left
    print right
    #exit()

    left = merge_sort(left)
    right = merge_sort(right)

    return merge(left, right)

def merge(left, right):
    result = []
    while len(left) > 0 and len(right) > 0:
        lv = left[0]
        rv = right[0]
        if lv <= rv:
            result.append(lv)
            left.pop(0)
        else:
            result.append(rv)
            right.pop(0)
    while len(left) > 0:
        result.append(left.pop(0))

    while len(right) > 0:
        result.append(right.pop(0))

    return result

A  = [20, 30, 21, 15, 42, 45, 31, 0, 9]

print A
print merge_sort(A)

理解するために、中間のパーティション分割された配列を出力しました。出力を確認してください。

[20, 30, 21, 15, 42, 45, 31, 0, 9]
[20, 30, 21, 15]
[42, 45, 31, 0, 9]
[20, 30]
[21, 15]
[20]
[30]
[21]
[15]
[42, 45]
[31, 0, 9]
[42]
[45]
[31]
[0, 9]
[0]
[9]
[0, 9, 15, 20, 21, 30, 31, 42, 45]

これがロジックを理解するのに役立つことを願っています。

于 2016-07-19T03:09:21.513 に答える