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
medianofmedianspartition!, but I include
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 = arr_view, 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 = arr, 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 = arr, 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 > a a, a = a, a end if a > a a, a = a, a end # We remove lowest of first 4 by comparing x1 and x3. if a < a a, a = a, a if a > a a, a = a, a end else a, a = a, a if a > a a, a = a, a end end # Now we have to find 2nd element out of x1 < x2, x3 < x4 if a < a if a < a a, a = a, a return else return end else if a < a a, a = a, a return else a, a = a, a return end end return end