Python Merge Art ohne

Question

Aufschneiden

Ive eine schnelle Art Implementierung ohne Aufschneiden zu schreiben versucht, aber ich bin mit Problemen mit der Mitte durch Laufzeit - ich gefragt, ob jemand mir zeigen konnte, wo ich falsch

gehe ich ein paar print-Anweisungen (Kommentar gesetzt), so können Sie sehen, was passiert vor und nach jeder Stufe hinzugefügt haben:

def mergesort(arr, l, r): 

    #print('start: ', arr[l:r]) 

    if len(arr[l:r]) <=1: 
     return arr[l:r] 

    mid = l + (r-l) // 2 
    left = mergesort(arr, l, mid) 
    right = mergesort(arr, mid, r) 

    l_idx = l 
    r_idx = mid 
    final = [] 

    while l_idx < mid and r_idx < r: 
     if arr[l_idx] <= arr[r_idx]: 
      final.append(arr[l_idx]) 
      l_idx+=1 
     else: 
      final.append(arr[r_idx]) 
      r_idx+=1 


    for val in arr[l_idx:mid]: 
     final.append(val) 

    for val in arr[r_idx:r]: 
     final.append(val) 

    #print('final: ', final[l:r]) 
    #print() 
    #print() 
    return final 



    print(merge([0, 9, 3, 7, 4, 2, 6, 1], 0, 8)) 

die Werte ich Show bekommen, dass für die linke Seite hatte es funktioniert gut, aber für das Recht es nicht. Das ist merkwürdig, weil es für die rechte Seite des linken scheint zu funktionieren ...

Die stdout ist:

start: [0, 9, 3, 7, 4, 2, 6, 1] 
start: [0, 9, 3, 7] 
start: [0, 9] 
start: [0] 
start: [9] 
final: [0, 9] 


start: [3, 7] 
start: [3] 
start: [7] 
final: [] 


final: [0, 3, 7, 9] 


start: [4, 2, 6, 1] 
start: [4, 2] 
start: [4] 
start: [2] 
final: [] 


start: [6, 1] 
start: [6] 
start: [1] 
final: [] 


final: [] 


final: [0, 4, 2, 6, 1, 9, 3, 7] 

Answer 1

Das Hauptproblem ist, dass Sie nie die left und right Listen verwenden Sie zurückgeschickt bekommen von den rekursiven Rufe, aber Sie brauchen diese, wie arr hat nicht ein einziges Bit durch diese Anrufe geändert. Und wenn Sie dies korrigieren, sollten Sie auch beachten, dass diese Ergebnisliste mit dem Index 0 beginnt, unabhängig von dem Wert l, den Sie über die rekursiven Aufrufe übergeben haben. Das bedeutet, dass die eigentliche Merging-Schleife bei Index 0 beginnen muss, nicht l.

Hier ist der Code, den Sie direkt nach der rekursiven Aufrufe haben sollte:

# concatenate the left and right results into arr 
arr = left + right 

# realign the indexes with the new arr 
mid -= l 
r -= l 
l_idx = 0 
r_idx = mid 

Mit dieser Änderung it will work.

NB: Sie haben gesagt, dass Sie dies ohne Slicing tun möchten, aber beachten Sie, dass Sie noch Slice: wenn Sie die : Notation, wie arr[l:r], schneiden Sie.