i´m relatively new to Julia and i´ve implemented the iterative form of the Bubble Sort and Insertion Sort algorithm in Julia.

I would like to know how can i implement the RECURSIVE form Bubble Sort and Insertion Sort in JULIA?

Thank you.

CodePudding user response：

Tail recursion would have helped here:

using BenchmarkTools

function bubblesort(arr::T) where T <: AbstractArray
    function recursebubble(a::T, remaining::T, sorted::T)
        if length(a) < 2
            if isempty(remaining)
                return [a ; sorted]
            else
                x = popfirst!(a)
                return recursebubble(remaining, T(), [x ; sorted])
            end
        else
            x = popfirst!(a)
            y = popfirst!(a)
            if x > y
                pushfirst!(remaining, y)
                pushfirst!(a, x)
            else
                pushfirst!(remaining, x)
                pushfirst!(a, y)
            end
            return recursebubble(a, remaining, sorted)
        end
    end
    recursebubble(copy(arr), T(), T())
end

function insertionsort(arr::T) where T <: AbstractArray
    function insert(a::T, x::eltype(T))
        if isempty(a)
            push!(a, x)
        else
            y = popfirst!(a)
            if x <= y
                pushfirst!(a, y)
                pushfirst!(a, x)
            else
                a = insert(a, x)
                pushfirst!(a, y)
            end
        end
        return a
    end
    function recursiveinsertion(a::T)
        isempty(a) && return a
        x = popfirst!(a)
        return insert(recursiveinsertion(a), x)
    end
    return recursiveinsertion(copy(arr))
end


randarray = rand(Int8, 100)

println("Recursive insertion: ", insertionsort(randarray))
@btime insertionsort(randarray)

println("Recursive bubble: ", bubblesort(randarray))
@btime bubblesort(randarray)

println("Base sort: ", sort(randarray))
@btime sort(randarray)

Recursive insertion: Int8[-126, -124, -124, -124, -108, -106, -105, -99, -98, -96, -95, -94, -89, -86, -85, -85, -83, -82, -79, -72, -66, -62, -59, -57, -56, -52, -42, -41, -37, -36, -35, -32, -26, -22, -18, -16, -10, -9, -6, -6, -2, -1, 2, 2, 3, 3, 5, 10, 10, 13, 13, 14, 17, 17, 17, 18, 19, 26, 26, 26, 27, 28, 30, 33, 35, 36, 37, 42, 45, 46, 48, 48, 51, 52, 53, 57, 60, 62, 63, 64, 68, 68, 71, 73, 80, 81, 93, 93, 93, 94, 96, 99, 104, 109, 113, 117, 120, 120, 121, 126]
194.500 μs (6 allocations: 640 bytes)
Recursive bubble: Int8[-126, -124, -124, -124, -108, -106, -105, -99, -98, -96, -95, -94, -89, -86, -85, -85, -83, -82, -79, -72, -66, -62, -59, -57, -56, -52, -42, -41, -37, -36, -35, -32, -26, -22, -18, -16, -10, -9, -6, -6, -2, -1, 2, 2, 3, 3, 5, 10, 10, 13, 13, 14, 17, 17, 17, 18, 19, 26, 26, 26, 27, 28, 30, 33, 35, 36, 37, 42, 45, 46, 48, 48, 51, 52, 53, 57, 60, 62, 63, 64, 68, 68, 71, 73, 80, 81, 93, 93, 93, 94, 96, 99, 104, 109, 113, 117, 120, 120, 121, 126]
391.400 μs (358 allocations: 26.84 KiB)
Base sort: Int8[-126, -124, -124, -124, -108, -106, -105, -99, -98, -96, -95, -94, -89, -86, -85, -85, -83, -82, -79, -72, -66, -62, -59, -57, -56, -52, -42, -41, -37, -36, -35, -32, -26, -22, -18, -16, -10, -9, -6, -6, -2, -1, 2, 2, 3, 3, 5, 10, 10, 13, 13, 14, 17, 17, 17, 18, 19, 26, 26, 26, 27, 28, 30, 33, 35, 36, 37, 42, 45, 46, 48, 48, 51, 52, 53, 57, 60, 62, 63, 64, 68, 68, 71, 73, 80, 81, 93, 93, 93, 94, 96, 99, 104, 109, 113, 117, 120, 120, 121, 126]
847.761 ns (1 allocation: 160 bytes)