Search code examples
algorithmrecursionjuliabubble-sortinsertion-sort

Recursive Bubble Sort and Insertion Sort in Julia


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.


Solution

  • 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)