BFPRT 알고리즘 및 python 구현

from mergeSort_recursion import mergesort
import random

def partion(a, m, m_index):
	# a    ，   m      m  ， m      m  
	#  ：m_index（m a  index）
	#  m  , m         ,  m      index
	
	# m            ，                 m     
	#      
	tmp = a[0]
	a[0] = m
	a[m_index] = tmp

	i = 0
	j = len(a)-1
	control_m = a[0]
	while i < j:
		while i< j and a[j] >= control_m:
			j -= 1

		a[i] = a[j]

		while i < j and a[i] <= control_m:
			i += 1
		a[j] = a[i]

	#  i = j， a[i]               
	a[i] = control_m
	print("m:{},after partion, a:{}".format(m, a))

	return i, len(a)-i-1, i


def bfprt(a, k):
	#  a  k    

	if len(a) < 5:
		#      5  ，    index k-1  ,   k    
		#                 ，         ，           
		mergesort(a,0, len(a)-1)
		return a[k-1]

	total_num = len(a)
	splits = total_num//5   #        

	#           
	split_medians = []
	for i in range(splits):
		cur = mergesort(a[i*5:(i+1)*5],0, 4)
		mid = cur[2]
		split_medians.append(mid)

	#    bfprt  ，         splits//2    ，          
	m = bfprt(split_medians, splits//2)
	#  m a  index
	m_index = [i for i in range(total_num) if a[i] == m][0]

	#  m a    ，     
	#num1， num2:  m      ，   m     
	num1, num2, m_index = partion(a, m, m_index)
	if k == num1+1:
		return m
	elif k <= num1:
		#   s1   
		return bfprt(a[:m_index], k)
	else:
		return bfprt(a[m_index+1:], k-1-m_index)


a = [5, 3, 1, 8, 2,10, 15, 18, 11,13, 16, 17, 12, 19, 0, 6, 4, 7, 9, 14]
random.shuffle(a)
k = 3
print(bfprt(a,7))

BFPRT 알고리즘 전체 사상:
1. 모든 n 개의 데 이 터 를 n / 5 (의 아래로 추출) 그룹 으로 나 누고 각 그룹 에 5 개의 요소 가 있 으 며, 병합 / 빠 른 정렬 로 각 그룹의 중위 수 (시간 복잡 도 * 5log 5 * n / 5, 즉 O (n) 를 구하 고, 재 귀적 으로 BFPRT 알고리즘 을 호출 하여 n / 5 개의 중위 수 (T (n / 5), 즉 n / 10 대 요 소 를 m 로 기록 하여 원 배열 에 있 는 m 의 위치 index (O (n) 를 찾 습 니 다.。
2. 원수 조 를 m 를 분계 점 으로 하고 m 보다 큰 num 2 개 원 소 를 m 오른쪽 에 놓 고 m 보다 작은 num 1 개 원 소 를 m 왼쪽 에 놓 습 니 다. 이때 m 의 새로운 위 치 는 index 입 니 다.new
        m 의 적당 한 위 치 를 찾기 전에 m 와 첫 번 째 요소 의 위 치 를 바 꿔 야 합 니 다.!!
3. k 와 num 1 을 비교 하면 k = num1 + 1 은 분계 점 m 가 바로 k 번 째 큰 요소 임 을 나타 낸다. 만약 에 k < = num 1 은 k 번 째 큰 요소 가 m 왼쪽 에 있다 는 것 을 나타 내 고 그 다음 에 m 왼쪽으로 가서 찾는다.그렇지 않 으 면 m 오른쪽 에서 m 오른쪽 에서 찾 아야 합 니 다.이렇게 해서 원래 의 문 제 를 규모 가 더 작은 문제 로 바 꾸 었 다.