Python quicksort rekursiven Tiefe

Question

ich zu finden bin versucht, wie weit die rekursive Funktion dh die tiefste Ebene der Rekursion absteigt, in der folgenden schnellen Art Code, habe ich gesagt, die qsort Funktion zu bearbeiten und jede Hilfe

schätzen würde

def partition(lst, lo, hi): 
    part = lo 
    while lo < hi: 
      while lst[lo] <= lst[part] and lo < hi: 
       lo += 1 
      while lst[hi] > lst[part]: # Don't have to check for hi >= 0 cos part is there as a sentinel. 
       hi -= 1 
      if lo < hi: 
       # Swap the two entries 
       lst[hi], lst[lo] = lst[lo], lst[hi] 
     # Swap part into position 
    if lst[part] > lst[hi]: # (this may happen of the array is small (size 2)) 
      lst[part], lst[hi] = lst[hi], lst[part] 
    print(part) 
    return hi 
def rec_qsort(lst, lo, hi): 
    if lo < hi: 
     pivot = partition(lst, lo, hi) 
     rec_qsort(lst, lo, pivot - 1) 
     rec_qsort(lst, pivot + 1, hi) 
def qsort(lst): 
    rec_qsort(lst, 0, len(lst) - 1) 
    return lst 

Answer 1

Übergeben Sie die Tiefe als optionalen Parameter, standardmäßig 0, an Ihre Implementierungsfunktion rec_qsort. Füge einen hinzu, wenn du tiefer rekrutierst.

def function(data, depth=0): 
    if len(data) > 1: 
     mid = len(data)/2 
     function(data[:mid], depth+1) 
     function(data[mid:], depth+1) 
    print "depth", depth, "length", len(data), data 

data = range(10) 
function(data) 

Offensichtlich am Anfang drucken, wenn Sie die Reihenfolge der Anrufe sehen möchten, am Ende drucken, wenn Sie sie, um durch wollen, wenn sie zurückkehren. Fügen Sie eine Uhr hinzu, anstatt zu drucken, wenn Sie beim Debuggen nur Tiefe sehen möchten.

von Benutzer pjs: Die maximale Tiefe von Quicksort, direkt gemessen, kann alles zwischen log (n) und n sein. Die erwartete Tiefe für randomisierte Daten oder ein zufällig ausgewähltes Pivot ist proportional zu log (n)