ピポット要素の特性 `7n/10`になることはあるのか

Question

###実現したいこと
中央値の中央値のアルゴリズムを作ってみました。
n個のリストについて考えます。
ここで再帰関数により選んだピポット要素より小さい値が7n/10ちょうどのときを探しています。
そのようになる値が出てくるようにリストとその要素数をランダムに作成しました。そしてそれを何回もシュミレーションするプログラムを作りました。しかし、ぴったり7n/10のとなるときは一度もありませんでした。
最大でも(7n/10)-1でした。
ぴったり7n/10となることはないのでしょうか。それかプログラムが間違っているのでしょうか。
###コード

#選択アルゴリズムk番目

import math
import random
def selection(a,k,num):
    #print("input:",a,"k =",k)
    n=len(a)
    small=[]
    smallb=[]
    pilist=[]
    def pivot(a,k):
        if n>=5:
            #先頭から５つずつに分けていく
            for i in range(0,n,5): #[0]から[n]まで5こずつ
                if i+4<n: #nが5の倍数ではない場合、最後は廃棄
                    start=i #分けた配列の最初の添え字
                    end=i+5 #分けた配列の最後の添え字
                    #print("start=",start,"end=",end)

                    small=a[start:end] #小配列を作る
                    smallb=sorted(small) #ソートした小配列
                    #print("smallb=",smallb)
                    #print("smallb[2]=",smallb[2])
                    pilist.append(smallb[2]) #ピポット要素の配列
                    small.clear()
                    smallb.clear()

            #ピポット要素の配列でさらに中央値を求める（再帰）
            k=len(pilist)/2.0
            pip=selection(pilist,math.ceil(k),num)
            #print("return:",pip)
        else:
            k=n/2.0
            k=math.ceil(k)
            pip=a[k]
            #print("returnpip:",pip)
        return pip
    n=len(a) #aのデータ数
    L=[]
    R=[]
    if n<5:
        b=sorted(a)
        #print("k=",k)
        #print("return:",b[k-1])
        return b[k-1]
    else:
        pi=pivot(a,k) #ピポット要素
        #分割する
        for i in range(n):
            if a[i]<pi:
                L.append(a[i])
            elif a[i]>pi:
                R.append(a[i])
        nL=len(L) #Lのデータ数
        nR=len(R) #Rのデータ数
        numi=(7*num)/10
        numi=math.floor(numi)
        #print("numi=",numi)
        if (numi-1)<=nL:
            print("num=",num)
            print("numi=",numi)
            print("☆☆☆nL=",nL)
            print("ピポット要素:",pi)
        #print("L=",L)

        #k番目を探す
        if k<=nL:
            ans=selection(L,k,num)
        elif nL==k-1:
            #print("return:",pi)
            return pi #ピポット要素がk番目
        else:
            #print("②")
            ans=selection(R,k-nL-1,num)
        #print("return:",ans)
        return ans

# 重複なし
def rand_ints_nodup(a, b, k):
  ns = []
  while len(ns) < k:
    n = 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))

Answer 1

以下の箇所で、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)

Comments

[langhtorn]

アドバイスありがとうございます。おかげで求めていた値が出てきました！！