Python - MergeSort Rekursionsfehlers

Question

Ich habe ein MergeSort Programm in Python Rekursion und ich halte Fehler über Linie 27, Linie 23, Linie 18 erhalten und eine Rekursionsfehlers:
„RecursionError: maximalen Rekursionstiefe im Vergleich überschritten“, aber ich scheint keinen offensichtlichen Fehler in meinem Code zu finden.

def merge(list, start, middle, end): 
    L = list[start:middle] 
    R = list[middle:end+1] 
    L.append(99999999999) 
    R.append(99999999999) 
    i = j = 0 
    for k in range(start, end+1): 
     if L[i] <= R[j]: 
      list[k] = L[i] 
      i += 1 
     else: 
      list[k] = R[j] 
      j+=1 

def mergesort2(list, start, end): 
    if start < end: 
     middle = (start + end)//2 
     mergesort2(list, start, end) 
     mergesort2(list, middle+1, end) 
     merge(list, start, middle, end) 

def mergesort(list): 
    mergesort2(list, 0, len(list)-1) 


mylist = [8,23,4,56,75,21,42,10,2,5] 
mergesort(mylist) 
print(mylist) 

Dank

Answer 1

def mergesort2(list, start, end): 
    if start < end: 
     middle = start + (end - start)//2 
     mergesort2(list, start, middle) // notice middle instead of end. 
     mergesort2(list, middle+1, end) 
     merge(list, start, middle, end) 

Sie wurden mit der gleichen Liste Rekursion ohne seine Größe zu reduzieren, so wurde es nie die Fallbasis zu erreichen.

Edit: Auch sollte Mitte von start + (end-start)/2 anstelle von (start+end)/2 berechnet werden, um Integer-Überlauf Fehler bei der Verwendung von großen Arrays zu vermeiden. Es ist eine gute Übung.

Bearbeiten 2: Nach der Analyse des Codes noch mehr, fand ich, dass die Ausgabe falsch war. Ich habe versucht, sie zu korrigieren und dies ist mein Code:

def merge(start, middle, end): 
    L = l[:middle] 
    R = l[middle:] 
    i = j = k = 0 
    while i < len(L) and j < len(R): 
     if L[i] <= R[j]: 
      l[k] = L[i] 
      i += 1 
     else: 
      l[k] = R[j] 
      j+=1 
     k += 1 
    while i < len(L): 
     l[k] = L[i] 
     i += 1 
     k += 1 
    while j < len(R): 
     l[k] = R[j] 
     j += 1 
     k += 1 

def mergesort2(start, end): 
    if start < end: 
     middle = start + (end - start)//2 
     mergesort2(start, middle) 
     mergesort2(middle+1, end) 
     merge(start, middle, end) 

def mergesort(l): 
    mergesort2(0, len(l)-1) 


l = [8,23,4,56,75,21,42,10,2,5] 
mergesort(l) 
print(l) 

Ein paar Punkte anzumerken:

• die Variablennamen list-l geändert Verwirrung zu vermeiden, die mit dem Schlüsselwort list.

• Es war nicht sinnvoll, die Liste an jede Funktion zu übergeben, da sie bereits als globale Variable deklariert wurde.

• merge() hatte einige Probleme. Die Schleife sollte eigentlich von 0 laufen, bis die Länge beider Listen nicht überschritten wird. Wenn es gekreuzt ist, kopieren Sie einfach die restlichen Elemente.

• Gebrauchte richtige Python Spleißtechniken :-P