Я написал сортировку слиянием, но она заканчивается бесконечным циклом - PullRequest
Новая
       38

Я написал сортировку слиянием, но она заканчивается бесконечным циклом

0 голосов
/ 05 апреля 2019

Если в первом раунде действует правило прерывания, программа останавливается, но когда она попадает в цикл, она никогда не останавливается 

def mSort(liste):
    mSortHelp(liste, 0, len(liste)-1)
return liste

def mSortHelp(liste, first, last):
    if first < last:
        mid = (first+last)//2
        mSortHelp(liste, mid, last)
        mSortHelp(liste, fist, mid)
        merge(liste, first, mid, last)
    return liste

def merge(liste, first, mid, last):
    LeftList = liste[first:mid]
    RightList =lListe[mid:last+1]
    i=j=0
    for k in range (first, last):
        if LeftList[i] <= RightList[j]:
            liste[k] = LeftList[i]
            i+=1
        else:
            liste[k] = RightList[j]
            j+=1
    return liste

print(mSort(liste))

Я надеюсь, что кто-нибудь может помочь исправить мой бесконечный цикл и вернуть отсортированный список (путем сортировки слиянием).

Ответы [ 2 ]

2 голосов
/ 05 апреля 2019

Во-первых, бесконечный цикл вызван if first < last:, например, если first = 2, last = 3, он никогда не пробьется, если вы измените его на first < last-1, это вызовет другую проблему, две длины список останется несортированным. Так что лучший способ решить эту проблему - не включать, например, [first, last).

И в вашей программе есть другие проблемы, такие как синтаксическая проблема, индекс вне диапазона при слиянии и другие проблемы. Я исправил их с комментарием: 

def mSort(liste):
    # change the last index
    # mSortHelp(liste, 0, len(liste) - 1)
    mSortHelp(liste, 0, len(liste))
    return liste

def mSortHelp(liste, first, last):
    # here is the key point causes infinit loop, such as first=2 last = 3
    # if first < last:
    if first < last - 1:
        mid = (first + last) // 2
        mSortHelp(liste, mid, last)
        mSortHelp(liste, first, mid)
        merge(liste, first, mid, last)
    return liste


def merge(liste, first, mid, last):
    LeftList = liste[first:mid]
    # change the last index
    # RightList = liste[mid:last + 1]
    RightList = liste[mid:last]
    i = j = 0

    print(LeftList, RightList)
    # here should be last, which means [first, last+1)
    for k in range(first, last):
        # here will cause "IndexError: list index out of range", if i or j reach the end
        # if LeftList[i] <= RightList[j]:
        if i < len(LeftList) and j < len(RightList):
            if LeftList[i] <= RightList[j]:
                liste[k] = LeftList[i]
                i += 1
            else:
                liste[k] = RightList[j]
                j += 1
        # when one list reach the end  
        else:
            if i < len(LeftList):
                liste[k] = LeftList[i]
                i += 1
            else:
                liste[k] = RightList[j]
                j += 1
    print(liste[first: last])
    # return is not necessary here, has been changed by parameter reference
    # return liste

Надеюсь, что это поможет вам, и прокомментируйте, если у вас есть дополнительные вопросы. :)

1 голос
/ 05 апреля 2019

Пример кода, где достижение конца любого подсписка обрабатывается в главном цикле слияния с последующим разрывом (вместо обработки копии после цикла). 

def mergesort(a,beg,end):
    if (end-beg) > 1:
        mid=(beg+end)//2
        mergesort(a,beg,mid)
        mergesort(a,mid,end)
        merge(a,beg,mid,end)
def merge(a,beg,mid,end):
    left = a[beg:mid]
    right = a[mid:end]
    i = 0
    j = 0
    k = beg   
    while True:
        if left[i] <= right[j]:
            a[k] = left[i]
            i += 1
            k += 1
            if(i < len(left)):
                continue
            a[k:end] = right[j:len(right)]
            break
        else:
            a[k] = right[j]
            j += 1
            k += 1
            if(j < len(right)):
                continue
            a[k:end] = left[i:len(left)]
            break
...