Effectively, factoring out the selectMedian function is quite usable for analysis of the algorithm by eliminating the recursive T(n/5) item.
As a result, T(n) <= T(7n/10) + Θ(n), in which Θ(n) is the expense of function partitionByPivot and function selectMedian(T(n) <= T(n/5) + Θ(n)).
So the inequality can be reduced to T(n) <= T(7n/10) + Θ(n) and result in Θ(10n/3), which is resolved by master method or reasoned out by recursion tree and geometric progression.
def swap(array:[], index1, index2):
array[index1], array[index2] = array[index2], array[index1]
def insertSort(array:[], startIndex:int, endIndex:int):
if startIndex >= endIndex:
return
for i in range(startIndex+1, endIndex+1):
target = array[i]
targetIndex = startIndex
for j in reversed(range(startIndex, i)):
if array[j] > target:
array[j+1] = array[j]
else:
targetIndex = j+1
break
array[targetIndex] = target
def partitionByPivot(array:[], startIndex:int, endIndex:int, pivot:int) -> int:
# Θ(n).
lastLessorIndex = startIndex - 1
pivotIndex = -1
for i in range(startIndex, endIndex+1):
if array[i] <= pivot:
lastLessorIndex += 1
swap(array, i, lastLessorIndex)
if array[lastLessorIndex] == pivot:
pivotIndex = lastLessorIndex
swap(array, pivotIndex, lastLessorIndex)
return lastLessorIndex
def selectMedian(array:[], startIndex:int, endIndex:int) -> int:
# Θ(n).
count = endIndex - startIndex + 1
if count > 5:
medians = []
i = startIndex
while i + 5 <= endIndex:
insertSort(array, i, i+4)
medians.append(array[i+2])
i += 5
insertSort(array, i, endIndex)
medians.append(array[(i+endIndex)//2])
return selectMedian(medians, 0, len(medians)-1)
insertSort(array, startIndex, endIndex)
return array[(startIndex+endIndex)//2]
def select(array:[], startIndex:int, endIndex:int, targetOrder:int) -> int:
if startIndex == endIndex:
return array[startIndex]
pivot = selectMedian(array, startIndex, endIndex)
pivotIndex = partitionByPivot(array, startIndex, endIndex, pivot)
targetIndex = startIndex + targetOrder
if pivotIndex == targetIndex:
return pivot
elif pivotIndex < targetIndex:
return select(array, pivotIndex+1, endIndex, targetIndex-pivotIndex-1)
else:
return select(array, startIndex, pivotIndex-1, targetOrder)
