Pythonのクイックソートは再帰的な深さ

Question

私は再帰関数には、次のクイックソートのコードでは、再帰の最も深いレベル、すなわち、下降どれだけ見つけるためにしようとしています

、私は、qソート機能を編集することが言われているし、任意の助けをいただければ幸いです

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

オプションパラメータとしてのパス深度（デフォルトは0）を実装関数rec_qsortに渡します。あなたが深く反省するときにそれを加えなさい。

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) 

明らかにあなたが呼び出しの順序を確認したい場合は、最初に印刷するあなたは、彼らが戻ったときにによって順序でそれらをしたい場合は最後に印刷します。デバッグ中に奥行きを見たい場合は、印刷する代わりに時計を追加します。

ユーザから：直接計測されたクイックソートの最大深度は、log（n）とnの間の任意の値にすることができます。無作為化されたデータまたは無作為に選択されたピボットの深さは、log（n）に比例します。