What is the difference between these two implementations?

New to Julia
,
1

I recently came across the programming language Julia, which is a very efficient language with a lot of tools that allow me to complete some tasks easily.
But I encountered a problem when learning how to use Julia to write a quick sort algorithm (using Hoare partition). In Wikipedia, Hoare partition is implemented using a do-while loop,which is not directly available in Julia, so I initially planned to use a basic while loop to avoid the do-while loop, and I had the following implementation:

begin
	function quick_sort_hoare(
		lst::Vector{N};
		lb::Integer = 1,
		ub::Integer = length(lst)
	)::Vector{N} where { N } 
		copied_lst = copy(lst)
		quick_sort_hoare!(copied_lst, lb, ub)
		copied_lst
	end

	function quick_sort_hoare!(lst::Vector{N}, lb::Integer, ub::Integer) where { N }
		if lb < 1 || ub < 1 || lb >= ub
			nothing
		else
			pivot_index = hoare_partition!(lst, lb, ub)
			quick_sort_hoare!(lst, lb, pivot_index)
			quick_sort_hoare!(lst, pivot_index + 1, ub)
		end
	end

	function hoare_partition!(
		lst::Vector{N},
		lb::Integer,
		ub::Integer
	)::Integer where { N }
		pivot = lst[lb]
		left_index = lb
		right_index = ub
		while true
			while lst[left_index] < pivot
				left_index = left_index + 1
			end
			while lst[right_index] > pivot
				right_index = right_index - 1
			end
			if left_index >= right_index
				break
			end
			lst[left_index], lst[right_index] = lst[right_index], lst[left_index]
		end
		right_index
	end
end

But the algorithm implemented above is very slow and may not even work properly, so I adjusted the loop implementation, which is the following code:

begin
	function quick_sort_hoare(
		lst::Vector{N};
		lb::Integer = 1,
		ub::Integer = length(lst)
	)::Vector{N} where { N } 
		copied_lst = copy(lst)
		quick_sort_hoare!(copied_lst, lb, ub)
		copied_lst
	end

	function quick_sort_hoare!(lst::Vector{N}, lb::Integer, ub::Integer) where { N }
		if lb < 1 || ub < 1 || lb >= ub
			nothing
		else
			pivot_index = hoare_partition!(lst, lb, ub)
			quick_sort_hoare!(lst, lb, pivot_index)
			quick_sort_hoare!(lst, pivot_index + 1, ub)
		end
	end

	function hoare_partition!(
		lst::Vector{N},
		lb::Integer,
		ub::Integer
	)::Integer where { N }
		pivot = lst[lb]
		left_index = lb - 1
		right_index = ub + 1
		while true
			while (left_index = left_index + 1; lst[left_index] < pivot) end
			while (right_index = right_index - 1; lst[right_index] > pivot) end
			if left_index >= right_index
				break
			end
			lst[left_index], lst[right_index] = lst[right_index], lst[left_index]
		end
		right_index
	end
end

The second implementation is correct, but I think the two implementations should be the same, so why is this?

Though the question may be very basic, I would appreciate guidance. Thank you in advance for your help.

2

Hi, and welcome to the Julia community!

The while loops in the two implementations are not equivalent, also when you take into account the different initialisations of left_index and right_index: in the second implementation you always increment left_index, while in the first one this only happens conditionally. For example,

julia> x = 10;

julia> while x <= 5
           x += 1  # equivalent to x = x + 1
       end

julia> x
10

compared to

julia> x = 10;

julia> while (x += 1; x <= 5) end

julia> x
11

Using the first implementation you can then get stuck in an infinite loop when lst[left_index] == pivot == lst[right_index], where you will keep swapping these (equal) list entries and never change left_index or right_index. You could fix the first implementation by explicitly adding a left_index += 1 and right_index -= 1 at the end of the loop:

function hoare_partition!(
    lst::Vector{N},
    lb::Integer,
    ub::Integer
    )::Integer where { N }
    pivot = lst[lb]
    left_index = lb
    right_index = ub
    while true
        while lst[left_index] < pivot
            left_index = left_index + 1
        end
        while lst[right_index] > pivot
            right_index = right_index - 1
        end
        if left_index >= right_index
            break
        end
        lst[left_index], lst[right_index] = lst[right_index], lst[left_index]
			
        left_index += 1    # <--------------
        right_index -= 1    # <--------------
    end
    right_index
end

As a side-note, it’s generally better to not specify variable types in functions if you don’t have to (e.g. you don’t use N in the body of your function). Additionally, the usual convention is to use T for a type (like Float64), and N for a natural number (e.g. 3, for example if you want to encode a length into the type of a struct, as in SVector from StaticArrays.jl).

1 Like
3

Thank you very much for your help. I finally understand where I went wrong!

In addition, you mentioned the type N. That was what I wanted to say that the type in Vector should be Comparable, but it seems that there is no similar interface or traits in Julia (I am not familiar with the corresponding term in Julia), so I forgot to remove it. Thanks for reminding me!

1 Like
4

This is a recurring theme. There are no built in traits or interfaces in julia, though there are some packages which creates things that mimics traits and interfaces. Julia typically uses “duck-typing”. If it behaves like a duck, it is a duck. In particular, elements of a type are comparable if the function Base.isless works for them, or < (if it’s a partial order). I.e. if you create your own type and want it to work with sorting and other algorithms doing comparisons, just define:

Base.isless(a::MyType, b::MyType) = mycomparisonfunction(a, b)
# or
Base.:(<)(a::MyType, b::MyType) = mycomparisonfunction(a, b)

https://docs.julialang.org/en/v1/base/sort/#Alternate-Orderings

2 Likes
5

Thank you for the documentation reference!