合并到位的python(不能找到错误的地方) [英] Merge Sort in place for python (Cant find what is wrong)

问题描述

我在我的算法书(算法第三版Cormen入门)中读到有关归类排序的信息，所以我决定用Python实现它.问题是我找不到我在做什么错...我在C ++中看到了一些代码，但是即使如此，我也无法修复它.

I was reading about merge sort(In place) in my algorithm book (Intro to algorithms 3rd edition Cormen), and I decided to implement it in Python. The problem is that I can't find what I am doing wrong... I saw some code in C++, but even with that I can't fix it.

这是我的代码:

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)]

运行代码时，我遇到了一些索引问题:

When I run the code I have some index problems:

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

我知道这是一个愚蠢的问题"，并且有一些相关的帖子，但是我尝试了其中的建议，但它对我不起作用...

I know that this my be a "dumb question" and that there is some related post, but I tried the suggestions in there and It does not work for me...

有人可以帮助我吗? Ť 谢谢！

Can anyone help me? T Thanks!

推荐答案

此代码可以正常工作:

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.

祝你好运！

(已添加)

您可以使用此代码检查除法过程.

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))

结果如下:

[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]

这就是我们想要的.但是，"mid + 1"会使结果无效.这是测试代码:

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))

结果:

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

---

(已添加)

---

(Added)

以下是使用"mid + 1"的代码:

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?

这篇关于合并到位的python(不能找到错误的地方)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！