ith order統計python（メディアンアプローチの中央値）

Question

dselectクイックソートの原理をピギーバックして、O（n）時間にソートされていないint（重複なし）の指定リストでi番目の順序統計を見つけます。 i番目の順序統計量は、指定されたリストのソートされたバージョンのi番目の最小要素として定義されます。だから、1次統計量が最小の要素とn次統計量が最大の要素だろうとそうで...

実行するには、私はdselect関数の最後にreturn arr[l]にIndexError: list index out of rangeを得るだろう。私はエラーdselectのmediansのリストの再帰呼び出しでを0としてハードコーディングしていると考えています。 （行4）

このエラーを回避するにはどうすればよいですか？その再帰呼び出しにはどのようにしてlの値を入れますか？それもこのエラーの原因ですか？これが愚かな質問であれば、それを指差して自由に感じてください。私はこの質問を削除します。私はちょうど私がかなり長い間これに固執してきたので、これを尋ねてきました。ありがとう。

def dselect(arr, l, r, i): 
    if l < r: 
     #finding pivot deterministically 
     medians = createMedianList(arr, l, r) 
     pivot = dselect(medians, 0, len(medians) - 1, len(medians) // 2) #line4 

     pivot = partition(arr, l, r, pivot) 
     if pivot + 1 == i: 
      return arr[pivot] 
     elif pivot + 1 > i: 
      return dselect(arr, l, pivot - 1, i) 
     else: 
      return dselect(arr, pivot + 1, r, i) 

    return arr[l] 

def partition(arr, l, r, pivot): 
    pivotIndex, i = arr.index(pivot), l 
    arr[l], arr[pivotIndex] = arr[pivotIndex], arr[l] 

    for j in range(l + 1, r + 1): 
     if arr[j] < arr[l]: 
      i += 1 
      arr[i], arr[j] = arr[j], arr[i] 
    arr[l], arr[i] = arr[i], arr[l] 

    return i 

def createMedianList(arr, l, r): 
    medians = [] 
    for i in range(l, (r + 1) - 5 + 1): 
     temp = sorted(arr[i:i + min(5, (r - l + 1) - i)]) 
     medians.append(temp[len(temp) // 2]) 

    return medians 

if __name__ == '__main__': 
    arr = [5, 2, 4, 3, 1, -1] 
    #arr = list(map(int, open('select.txt').read().splitlines())) 
    print(dselect(arr, 0, len(arr) - 1, int(input('Which order 
    statistic to find? ')))) 

Answer 1

問題は時々空のリストを返しますcreateMedianListことです： 最終的に起こるであろうl >= r-3場合、これが発生します。 createMedianListに何かを追加して、空のリストを返さないようにすることをお勧めします。 例：if medians==[]:medians=[arr[0]]またはそれに類するもの（中央値に対してどのプロパティを使用したいかによって異なります）。