質問: random.randint(a, b) if not n in ns: ns.append(n) return ns a=[] #リスト #リストに入力していく for i in range(1000): num=random.randint(20,50) #リスト数 #print("num=",num) a=rand_ints_nodup(0,100,num) #リストの中身 print("a=",a) k=random.randint(1,num) print("answer:",selection(a,k,num)) ```
回答: 以下の箇所で、pilistの長さが偶数の時、常に中央2つの小さい側をpivotに採用しているので、 pivotより小さい値の数が少なくなる方に偏るのでしょう。 ``` #ピポット要素の配列でさらに中央値を求める(再帰) k=len(pilist)/2.0 pip=selection(pilist,math.ceil(k),num) ``` 偶数の時、常に中央2つの大きい側をpivotに採用するようにすれば、 長さが10の倍数のときにぴったり7n/10になる可能性が出てきます。 ``` #ピポット要素の配列でさらに中央値を求める(再帰) k=(len(pilist)+1)/2.0 pip=selection(pilist,math.ceil(k),num) ```