I’m implementing basically the Median of Medians (actually, Median of Ninthers) algorithm for quick deterministic selection (see [original post]). It is recursive, as in the way to find a pivot is by calculating the median of ninthers of chunks of the array and that median is found by calling the medianofninthers of those ninthers.
I keep reading that Julia is not great with recursion and that TCO is not well supported, and that I should make the calls iterative instead of recursive, but then I see that Quick Sort implementation (which in essence is very similar to median of medians, but with a different pivot finding algorithm and of course without sorting) is recursive.
If I could gain some clarity on what the right approach is here, I’d really appreciate it!
For reference, this is the medianofmedians! function and the functions it calls (the recursion happens between quickselect! and medianofmedianspartition!, but I include hoarepartition! and medianoffive! for completeness, note that only hoarepartition uses inbounds macro because i’m still learning how and where to use).
(note: In the last post I was asked to add more code, please let me know if I’m going overboard here, I’m still figuring out the etiquette here.)
function medianofmedianspartition!(arr::AbstractVector)
len = length(arr)
if len < 5
sort!(arr)
return 1 + len ÷ 2
end
j = 1
i = 1
while i + 4 <= len
arr_view = @view(arr[i:(i+4)])
medianoffive!(arr_view)
arr[j], arr_view[3] = arr_view[3], arr[j]
i += 5
j += 1
end
j -= 1
quickselect!(@view(arr[1:j]), 1 + j ÷ 2, medianofmedianspartition!)
return hoarepartition!(arr, 1 + j ÷ 2)
end
function quickselect!(arr::AbstractVector, position::Integer, partitionfunc!::Function)
i = 1
j = length(arr)
if i == j
return
end
while true
new_position = i + partitionfunc!(@view(arr[i:j])) - 1
if new_position == position
return
elseif new_position > position
j = new_position - 1
else
i = new_position + 1
end
end
return
end
function hoarepartition!(arr::AbstractVector, pivot_index::Integer)
@inbounds pivot_value = arr[pivot_index]
@inbounds arr[pivot_index], arr[1] = arr[1], arr[pivot_index]
a = 2
b = length(arr)
@inbounds while a < b
while a <= b && arr[a] <= pivot_value
a += 1
end
while pivot_value < arr[b]
b -= 1
end
if a >= b
break
end
arr[a], arr[b] = arr[b], arr[a]
a += 1
b -= 1
end
@inbounds arr[a-1], arr[1] = arr[1], arr[a-1]
return a - 1
end
function medianoffive!(a::AbstractVector)
@assert length(a) == 5 "medianoffive! only works for arrays of 5 elements."
# We order x1 < x2 and x3 < x4
if a[1] > a[2]
a[1], a[2] = a[2], a[1]
end
if a[3] > a[4]
a[3], a[4] = a[4], a[3]
end
# We remove lowest of first 4 by comparing x1 and x3.
if a[1] < a[3]
a[1], a[5] = a[5], a[1]
if a[1] > a[2]
a[1], a[2] = a[2], a[1]
end
else
a[3], a[5] = a[5], a[3]
if a[3] > a[4]
a[3], a[4] = a[4], a[3]
end
end
# Now we have to find 2nd element out of x1 < x2, x3 < x4
if a[1] < a[3]
if a[2] < a[3]
a[2], a[3] = a[3], a[2]
return
else
return
end
else
if a[4] < a[1]
a[4], a[3] = a[3], a[4]
return
else
a[1], a[3] = a[3], a[1]
return
end
end
return
end
. Or maybe it’s done and I haven’t found it.